Patent US5282214A successfully refreshed from Google Patents.
US5282214A
Expired / Lapsed
US
⏱️ 0.0 years remaining
Apparatus and method for parallel generation of cyclic redundancy check (CRC) codes
Assignee: Nokia Bell Labs
•
Filing: 1993-03-01
•
Granted: 1994-01-25
•
Expires: 2013-03-01
Abstract
Abstract A method and apparatus are disclosed for the efficient generation of cyclic redundancy check (CRC) codes employing CRC generator polynomials of the form (1+x)·f(x). The efficiency is achieved by independently and concurrently generating in parallel a preliminary CRC code word corresponding to f(x) and a term corresponding to (1+x) over a message M(x). The term corresponding to (1+x) is generated in a manner to have either a zero (0) state or a one (1) state. Then, the term corresponding to (1+x) is used to modify the preliminary CRC code word to obtain an overall CRC code word being generated over message M(x). If the term corresponding to (1+x) is a 0 state, then the overall CRC code word is obtained by shifting the bits of the preliminary CRC code word once to the left. If the term corresponding to (1+x) is a 1 state, then the overall CRC code word is obtained by shifting the bits of the preliminary CRC code word once to the left and adding f(x) to the shifted preliminary CRC code word.
Inventors
- 👤 Subrahmanyam Dravida
Bibliographic Details
Application Number
—
Jurisdiction
US
Data Source
google_patents
Last Synchronized
2026-11-01 17:40
CPC Classifications
H; H03; H03M; H03M13/00; H03M13/03; H03M13/05; H03M13/09; H03M13/091; H03M13/65; H03M13/6575
Claims Analysis
Total Claims: 16
Claim 1
Independent Claim
249 words
A method for a parallel generation of a digital representation of an overall cyclic redundancy check (CRC) code word of a form (1×x)·f(x) for a message M(x), comprising steps of: interfacing to a transmission path to obtain blocks of bits A i in parallel of the message M(x); simultaneously loading each bit within a given block of bits A i into a specific one of a plurality of input ports of a first combinational logic circuit which independently generates a digital representation of a preliminary CRC code word using a digital representation of a polynomial f(x) in response to said given block of bits A i of said message M(x); simultaneously loading each bit within said given block of bits A i into a specific one of a plurality of input ports of a second combinational logic circuit which independently generates a digital representation of a term corresponding to a factor of (1+x) in response to said given block of bits A i of said message M(x); and providing said digital representation of said preliminary CRC code word generated by said first combinational logic circuit and said digital representation of said term corresponding to said (1×x) factor generated by said second combinational logic circuit to a third combinational logic circuit which modifies said digital representation of said preliminary CRC code in a prescribed manner in response to said digital representation of said term corresponding to said (1×x) factor to obtain said digital representation of said overall CRC code word.
Claim 2
Independent Claim
249 words
A method for a parallel generation of a digital representation of an overall cyclic redundancy check (CRC) code word of a form (1×x)·f(x) for a message M(x), comprising steps of: interfacing to a transmission path to obtain blocks of bits A i in parallel of the message M(x); simultaneously loading each bit within a given block of bits A i into a specific one of a plurality of input ports of a first combinational logic circuit which independently generates a digital representation of a preliminary CRC code word using a digital representation of a polynomial f(x) in response to said given block of bits A i of said message M(x); simultaneously loading each bit within said given block of bits A i into a specific one of a plurality of input ports of a second combinational logic circuit which independently generates a digital representation of a term corresponding to a factor of (1+x) in response to said given block of bits A i of said message M(x); and providing said digital representation of said preliminary CRC code word generated by said first combinational logic circuit and said digital representation of said term corresponding to said (1×x) factor generated by said second combinational logic circuit to a third combinational logic circuit which modifies said digital representation of said preliminary CRC code in a prescribed manner in response to said digital representation of said term corresponding to said (1×x) factor to obtain said digital representation of said overall CRC code word.
Claim 3
Dependent Claim
98 words
The method as defined in claim 1, wherein said step of simultaneously loading each bit within a given block of bits A i into a specific one of a plurality of input ports of said first combinational logic circuit and generating said digital representation of said preliminary CRC code word, and said step of simultaneously loading each bit within a given block of bits A i into a specific one of a plurality of input ports of said second combinational logic circuit and generating said digital representation of said term corresponding to said (1×x) factor, are performed concurrently.
Claim 4
Dependent Claim
31 words
The method as defined in claim 2, wherein said generated digital representation of said term corresponding to said (1×x) factor has either a first prescribed state or a second prescribed state.
Claim 5
Dependent Claim
89 words
The method as defined in claim 3, wherein said third combinational logic circuit which modifies said digital representation of said preliminary CRC code includes modifying said digital representation of said preliminary CRC code word in a first prescribed manner when said digital representation of said term corresponding to said (1×x) factor has said first prescribed state and modifying said digital representation of said preliminary CRC code word in a second prescribed manner when said term corresponding to said digital representation of said (1+x) factor has said second prescribed state.
Claim 6
Dependent Claim
113 words
The method as defined in claim 4, wherein said first prescribed state is a logical 0 and said second prescribed state is a logical 1, and wherein said first prescribed manner of modifying said digital representation of said preliminary CRC code word comprises shifting the bits of said digital representation of said preliminary CRC code word once to the left, and wherein said second prescribed manner of modifying said digital representation of said preliminary CRC code word comprises shifting the bits of digital representation of said preliminary CRC code word once to the left and adding a digital representation of polynomial f(x) to the shifted digital representation of said preliminary CRC code word.
Claim 7
Dependent Claim
69 words
The method as defined in claim 5, wherein said digital representation of said preliminary CRC code word is generated within said first combinational logic circuit in accordance with a remainder ##EQU10## where R'(x) is the preliminary CRC code word, M(x) is the message over which the overall CRC code word is being generated, (r) is a degree of the polynomial (1+x)·f(x), and (r-1) is a degree of polynomial f(x).
Claim 8
Dependent Claim
54 words
The method as defined in claim 6, wherein said digital representation of said term corresponding to said (1+x) factor is generated within said second combinational logic circuit in accordance with a remainder ##EQU11## where R"(x) is the term corresponding to said (1×x) factor and Q'(x) is a quotient polynomial obtained from said message M(x).
Claim 9
Dependent Claim
238 words
Apparatus for a parallel generation of a digital representation of an overall cyclic redundancy check (CRC) code word of a form (1×x)·f(x) for a message M(x), comprising: means for interfacing to a transmission path to obtain blocks of bits A i in parallel of the message M(x); first combinational logic circuit for simultaneously receiving each bit within a given block of bits A i from said interface means into a specific one of a plurality of input ports of said first combinational logic circuit, said first combinational logic circuit independently generating a digital representation of a preliminary CRC code word according to a digital representation of a polynomial f(x) in response to said given block of bits A i of said message M(x); second combinational logic circuit for simultaneously receiving each bit within said given block of bits A i from said interface means into a specific one of a plurality of input ports of said second combinational logic means, said second combinational logic means independently generating a digital representation of a term corresponding to a factor of (1+x) in response to said given block of bits A i of said message M(x); and third combinational logic circuit responsive to said generated digital representation of said term corresponding to a (1+x) factor for modifying said digital representation of said preliminary CRC code word in a prescribed manner to obtain said digital representation of said overall CRC code word.
Claim 10
Dependent Claim
238 words
Apparatus for a parallel generation of a digital representation of an overall cyclic redundancy check (CRC) code word of a form (1×x)·f(x) for a message M(x), comprising: means for interfacing to a transmission path to obtain blocks of bits A i in parallel of the message M(x); first combinational logic circuit for simultaneously receiving each bit within a given block of bits A i from said interface means into a specific one of a plurality of input ports of said first combinational logic circuit, said first combinational logic circuit independently generating a digital representation of a preliminary CRC code word according to a digital representation of a polynomial f(x) in response to said given block of bits A i of said message M(x); second combinational logic circuit for simultaneously receiving each bit within said given block of bits A i from said interface means into a specific one of a plurality of input ports of said second combinational logic means, said second combinational logic means independently generating a digital representation of a term corresponding to a factor of (1+x) in response to said given block of bits A i of said message M(x); and third combinational logic circuit responsive to said generated digital representation of said term corresponding to a (1+x) factor for modifying said digital representation of said preliminary CRC code word in a prescribed manner to obtain said digital representation of said overall CRC code word.
Claim 11
Dependent Claim
45 words
The apparatus as defined in claim 8, wherein said first combinational logic circuit, and said second combinational logic circuit operate concurrently to respectively generate said digital representation of said preliminary CRC code word and said digital representation of said term corresponding to said (1+x) factor.
Claim 12
Dependent Claim
37 words
The apparatus as defined in claim 9, wherein said digital representation of said term corresponding to said (1×x) factor generated by said second combinational logic circuit has either a first prescribed state or a second prescribed state.
Claim 13
Dependent Claim
83 words
The apparatus as defined in claim 10, wherein said third combinational logic circuit includes means for modifying said digital representation of said preliminary CRC code word in a first prescribed manner when said digital representation of said term corresponding to said (1×x) factor has said first prescribed state and means for modifying said digital representation of said preliminary CRC code word in a second prescribed manner when said digital representation of said term corresponding to said (1+x) factor has said second prescribed state.
Claim 14
Dependent Claim
115 words
The apparatus as defined in claim 11, wherein said first prescribed state is logical 0 and said second prescribed state is a logical 1, and wherein said first prescribed manner of modifying said digital representation of said preliminary CRC code word within said third combinational logic circuit comprises shifting the bits of said digital representation of said preliminary CRC code word once to the left, and wherein said second prescribed manner of modifying said digital representation of said preliminary CRC code word within said third combinational logic circuit comprises shifting said bits once to the left and adding a digital representation of polynomial f(x) to the shifted digital representation of said preliminary CRC code word.
Claim 15
Dependent Claim
70 words
The apparatus as defined in claim 12, wherein said first combinational logic circuit includes means for generating said digital representation of said preliminary CRC code word in accordance with a remainder ##EQU12## where R'(x) is the preliminary CRC code word, M(x) is the message over which the overall CRC code word is being generated, (r) is a degree of the polynomial (1×x)·f(x), and (r-1) is a degree of polynomial f(x).
Claim 16
Dependent Claim
44 words
The apparatus as defined in claim 13, wherein said second combinational logic circuit includes means for generating said digital representation of said term corresponding to said (1×x) factor in accordance with a remainder ##EQU13## where R"(x) is the term corresponding to said (1×x) factor.
References Cited (Backward Citations)
US3805232A
Cited
US4312068A
Cited
US4498178A
Cited
US4454600A
Cited
US4498174A
Cited
US4677623A
Cited
US4593393A
Cited
US4809273A
Cited
US4890286A
Cited
US5121396A
Cited
US5111463A
Cited
US5103451A
Cited
USPTO Annuity & Maintenance Windows
| Annuity Stage | Window Opens | Payment Deadline | Surcharge Period Until | Estimated Fee | Status |
|---|---|---|---|---|---|
| 3.5 Years (Year 4) | 1997-01-24 | 1997-07-26 | 1998-01-25 | $2000.00 | Window Closed / Lapsed |
| 7.5 Years (Year 8) | 2001-01-24 | 2001-07-26 | 2002-01-25 | $3760.00 | Window Closed / Lapsed |
| 11.5 Years (Year 12) | 2005-01-24 | 2005-07-26 | 2006-01-25 | $7700.00 | Window Closed / Lapsed |