Cyclic redundancy check modification for message length detection and error detection

• US 20050257118A1
• Filed: 05/13/2004
• Published: 11/17/2005
• Est. Priority Date: 05/13/2004
• Status: Active Grant

• Current Assignee: National Chiao Tung University (Government of The Republic of China), Industrial Technology Research Institute
• Original Assignee: Industrial Technology Research Institute
• Inventors: Shien, Shin-Lin
• Granted Patent: US 7,240,273 B2
• Time in Patent Office: Days
• US Class Current: 714/758
• CPC Class Codes: H03M 13/09 Error detection only, e.g. using cyclic redundancy check [CRC] codes or single parity bit

Abstract

In a method for a variable-length communications system including encoding a message and decoding a data bit stream, the message includes a plurality of message blocks. A message block of the message is encoded by generating a parity check bit stream, flipping the parity check bit stream, and appending the flipped parity check bit stream to the end of the message block. When a data bit stream is received, a guessed message block and a guessed flipped parity check bit stream are extracted based on a guessed message block length. A parity check bit stream is generated for the guessed message block and then flipped. If the flipped parity check bit stream is the same as the guessed flipped parity check bit stream, the message block has been identified. Otherwise, the guessed message block length is increased by 1 and the above step is repeated.

Claims

1. A method for a variable-length communications system, wherein messages to be transmitted are divided into variable-length message blocks, the method comprising:

providing a cyclic redundancy check (CRC) generating polynomial g_l(x), wherein l is an integer and is the order of g_l(x);

providing a binary flip polynomial f_l(x) having an order of l−

1, wherein f_l(x)=f_l-1x^l-1+f_l-2x^l-2+ . . . +f₀; and

encoding a message block M of a message to be transmitted, wherein M includes k binary bits, m_k-1, m_k-2, . . . , m₀, and wherein encoding M includes

generating a parity check bit stream P, wherein P includes l parity check bits, p_l-1, p_l-2, . . . , p₀, such that g_l(x)|(x^lM(x)+P(x)), wherein M(x)=m_k-1x^k-1+m_k-2x^k-2+ . . . +m₀, and P(x)=p_l-1x^l-1+p_l-2x^l-2+ . . . +p₀,

flipping the parity check bit stream P to generate a flipped parity check bit stream {overscore (P)} including l flipped parity check bits {overscore (p_l-1)}, {overscore (p_l-2)}, . . . , {overscore (p₀)}, such that {overscore (p_i-1)}=p_l-1+f_l-1, {overscore (p_l-2)}=p_l-2+f_l-2, . . . , {overscore (p₀)}=p₀+f₀, wherein “

+”

is a modulo-2 addition operation, and

appending the flipped parity check bit stream {overscore (P)} to the end of message block M to create a concatenated bit stream C, such that C includes k+1 bits, m_k-1, m_k-2, . . . , m₀, {overscore (p_l-1)}, {overscore (p_l-2)}, . . . , {overscore (p₀)}.

2. The method of claim 1, wherein CRC generating polynomial g_l(x) is chosen such that gcd(g_l(x),xⁱ)=1 for 0≦

i≦

l, wherein i is an integer.

3. The method of claim 1, wherein flip polynomial f_l(x) is chosen such that

$\mathrm{deg}$

( remainder ⁢

 

⁢

of ⁡

( ( 1 + x i ) ⁢

f l ⁡

( x ) g l ⁡

( x ) ) ) ≥

i ,

for 1≦

i≦

l−

1, wherein i is an integer.

4. The method of claim 1, further comprising repeating the encoding to create a concatenated bit stream for each message block of the messages to be transmitted and transmitting the concatenated bit streams in series.

5. A method for a variable-length communications system, wherein the system includes a receiver, the method comprising:

storing in the receiver information of a cyclic redundancy check (CRC) generating polynomial g_l(x), wherein l is an integer and is the order of g_l(x), and information of a flip polynomial f_l(x) having an order of l−

1;

receiving a data bit stream including a plurality of concatenated bit streams, each concatenated bit stream consisting of a message block and a corresponding flipped parity check bit stream; and

identifying a first message block in the data bit stream, including

(a) guessing a message block length {circumflex over (k)} and a message block M′

consisting of the first {circumflex over (k)} bits in the data bit stream,

$m_{\hat{k}-1}^{\mathrm{\prime <br><br>}},m_{\hat{k}-2}^{\mathrm{\prime <br><br>}},\mathrm{\dots <br><br>}<br><br>\text{\hspace{1em}<br><br>},m_0^{\mathrm{\prime <br><br>}},$

wherein {circumflex over (k)} is an integer, and wherein l bits in the data bit stream that immediately follow the message block M′

compose a guessed flipped bit stream P′

,

(b) generating a parity check bit stream {circumflex over (P)} including l parity check bits, {circumflex over (p)}_l-1, {circumflex over (p)}_l-2, . . . , {circumflex over (p)}₀, such that g_l(x)|(x^lM′

(x)+{circumflex over (P)}(x)), wherein

$M^{\mathrm{\prime <br><br>}}<br><br>\left(x\right)=m_{\hat{k}-1}^{\mathrm{\prime <br><br>}}<br><br>x^{\hat{k}-1}+m_{\hat{k}-2}^{\mathrm{\prime <br><br>}}<br><br>x^{\hat{k}-2}+\mathrm{\cdots <br><br>}+m_0^{\mathrm{\prime <br><br>}},\mathrm{and}$$\hat{P}<br><br>\left(x\right)={\hat{p}}_{l-1}<br><br>x^{l-1}+{\hat{p}}_{l-2}<br><br>x^{l-2}+\mathrm{\cdots <br><br>}+{\hat{p}}_0,$

(c) flipping the parity check bit stream {circumflex over (P)} using flip polynomial f_l(x) to generate a flipped parity check bit stream {circumflex over (P)}′

including l flipped parity check bits, {circumflex over (p)}′

_l-1, {circumflex over (p)}′

_l-2, . . . , {overscore (p)}′

₀, and

(d) if P′ and

{circumflex over (P)}′

are different, increasing {circumflex over (k)} by 1 and repeating (a)-(c).

6. The method of claim 5, wherein CRC generating polynomial g_l(x) satisfies gcd(g_l(x),xⁱ)=1 for 0≦

i≦

l, wherein i is an integer.

7. The method of claim 5, wherein flip polynomial f_l(x) satisfies

$\mathrm{deg}$

( remainder ⁢

 

⁢

of ⁡

( ( 1 + x i ) ⁢

f l ⁡

( x ) g l ⁡

( x ) ) ) ≥

i ,

for 1≦

i≦

l−

1, wherein i is an integer.

8. The method of claim 5, wherein the length of the first message block is k, wherein k is an integer, and the initial value of {circumflex over (k)} is not greater than k.

9. The method of claim 5, wherein the flipped parity check bit stream {circumflex over (P)}′

is generated such that

${\hat{p}}_{l-1}^{\mathrm{\prime <br><br>}}={\hat{p}}_{l-1}+f_{l-1},{\hat{p}}_{l-2}^{\mathrm{\prime <br><br>}}={\hat{p}}_{l-2}+f_{l-2},\mathrm{\dots <br><br>}<br><br>\text{\hspace{1em}<br><br>},{\hat{p}}_0^{\mathrm{\prime <br><br>}}={\hat{p}}_0+f_0,$

wherein “

+”

is a modulo-2 addition operator.

10. The method of claim 5, wherein identifying the first message block further comprising removing the first {circumflex over (k)}+l bits from the data bit stream when P′

={circumflex over (P)}′

.

11. The method of claim 10, further comprising repeating identifying the first message block in the data bit stream after the first {circumflex over (k)}+l bits are removed.

12. A method for a variable-length communications system, wherein the system includes a transmitter and a receiver, wherein messages are divided into variable-length message blocks, comprising:

providing a cyclic redundancy check (CRC) generating polynomial g_l(x), wherein l is an integer and is the order of g_l(x);

providing a binary flip polynomial f_l(x) having an order of l−

1;

storing in both the transmitter and the receiver information of CRC generating polynomial g_l(x) and information of flip polynomial f_l(x);

encoding a message to be transmitted by encoding each message block M thereof, wherein encoding M includes

generating a parity check bit stream P using the CRC generating polynomial g_l(x),

flipping the parity check bit stream P to generate a flipped parity check bit stream {overscore (P)} using flip polynomial f_l(x), and

appending the flipped parity check bit stream {overscore (P)} to the end of the message block M to create a concatenated bit stream C; and

transmitting the concatenated bit streams C of the message blocks M of the message to be transmitted;

receiving a data bit stream including a plurality of concatenated bit streams, each concatenated bit stream consisting of a message block and a corresponding flipped parity check bit stream; and

decoding the data bit stream, including

identifying a first message block in the data bit stream, including

(a) guessing a message block length {circumflex over (k)} and a message block M′

consisting of the first {circumflex over (k)} bits in the data bit stream,

$m_{\hat{k}-1}^{\mathrm{\prime <br><br>}},m_{\hat{k}-2}^{\mathrm{\prime <br><br>}},\mathrm{\dots <br><br>}<br><br>\text{\hspace{1em}<br><br>},m_0^{\mathrm{\prime <br><br>}},$

 

wherein {circumflex over (k)} is an integer, and wherein l bits in the data bit stream that immediately follow the message block M′

compose a guessed flipped bit stream P′

,

(b) generating a parity check bit stream {circumflex over (P)} using CRC generating polynomial g_l(x),

(c) flipping the parity check bit stream {circumflex over (P)} using flip polynomial f_l(x) to generate a flipped parity check bit stream {circumflex over (P)}′

,

(d) if P′ and

{circumflex over (P)}′

are different, increasing {circumflex over (k)} by 1 and repeating (a)-(c), and

(e) removing the first {circumflex over (k)}+l bits from the data bit stream when P′

={circumflex over (P)}′

, and

repeating the identifying of the first message block in the data bit stream after the first {circumflex over (k)}+l bits are removed.

13. The method of claim 12, wherein the CRC generating polynomial g_l(x) is chosen such that gcd(g_l(x),xⁱ)=1 for 0≦

i≦

l, wherein i is an integer.

14. The method of claim 13, wherein the parity check bit stream {circumflex over (P)} includes l bits, {circumflex over (p)}_l-1, {circumflex over (p)}_l-2, . . . , {circumflex over (p)}₀, and is generated such that g_l(x)|(x^lM′

(x)+{circumflex over (P)}(x)), wherein

$M^{\mathrm{\prime <br><br>}}<br><br>\left(x\right)=m_{\hat{k}-1}^{\mathrm{\prime <br><br>}}<br><br>x^{\hat{k}-1}+m_{\hat{k}-2}^{\mathrm{\prime <br><br>}}<br><br>x^{\hat{k}-2}+\mathrm{\dots <br><br>}+m_0^{\mathrm{\prime <br><br>}},<br><br>\mathrm{and}$ $\hat{P}<br><br>\left(x\right)={\hat{p}}_{l-1}<br><br>x^{l-1}+{\hat{p}}_{l-2}<br><br>x^{l-2}+\mathrm{\dots <br><br>}+{\hat{p}}_0.$

15. The method of claim 12, wherein flip polynomial f_l(x) is chosen such that

$\mathrm{deg}$

( remainder ⁢

 

⁢

of ⁢

 

⁢

( ( 1 + x i ) ⁢

f l ⁡

( x ) g l ⁡

( x ) ) ) ≥

i ,

for 1≦

i≦

l−

1, wherein i is an integer.

16. The method of claim 15, wherein the parity check bit stream {circumflex over (P)} includes l bits, {circumflex over (p)}_l-1, {circumflex over (p)}_l-2, . . . , {circumflex over (p)}₀, wherein the flipped parity check bit stream includes {circumflex over (P)}′

including l flipped parity check bits,

${\hat{p}}_{l-1}^{\mathrm{\prime <br><br>}},{\hat{p}}_{l-2}^{\mathrm{\prime <br><br>}},\mathrm{\dots <br><br>}<br><br>\text{\hspace{1em}<br><br>},{\hat{p}}_0^{\mathrm{\prime <br><br>}},$

and wherein the flipped parity check bit stream {circumflex over (P)}′

is generated such that

${\hat{p}}_{l-1}^{\mathrm{\prime <br><br>}}={\hat{p}}_{l-1}+f_{l-1},{\hat{p}}_{l-2}^{\mathrm{\prime <br><br>}}={\hat{p}}_{l-2}+f_{l-2},\mathrm{\dots <br><br>}<br><br>\text{\hspace{1em}<br><br>},{\hat{p}}_0^{\mathrm{\prime <br><br>}}={\hat{p}}_0+f_0,$

wherein “

+”

is a modulo-2 addition operator.

17. The method of claim 12, wherein the length of the first message block in the data bit stream is k, wherein k is an integer, and the initial value of {circumflex over (k)} is not greater than k.