Method and apparatus for encoding of linear block codes

• US 6,763,492 B1
• Filed: 09/26/2000
• Issued: 07/13/2004
• Est. Priority Date: 09/26/2000
• Status: Expired due to Fees

• Current Assignee: Qualcomm, Inc.
• Original Assignee: Qualcomm, Inc.
• Inventors: Levin, Jeffrey A., Schlegel, Nikolai, Hurt, James Y.
• Primary Examiner(s): Decady, Albert
• Assistant Examiner(s): CHAUDRY, MUJTABA M
• Application Number:
  US09/671,372
• Time in Patent Office: 1,386 Days
• Field of Search: 714/759, 714/752, 714/779, 714/758, 714/751, 714/800, 714/746, 714/699
• US Class Current: 714/752
• CPC Class Codes: H03M 13/096 Checksums
• CPC Class Codes: H03M 13/15 Cyclic codes, i.e. cyclic shifts of codewords produce other codewords, e.g. codes defined by a generator polynomial, Bose-Chaudhuri-Hocquenghem [BCH] codes H03M13/17 takes precedence
• CPC Class Codes: H03M 13/47 Error detection, forward error correction or error protection, not provided for in groups H03M13/01 - H03M13/37
• CPC Class Codes: H04L 1/0041 Arrangements at the transmitter end
• CPC Class Codes: H04L 1/0057 Block codes H04L1/0061, H04L1/0064 take precedence

Abstract

A method and apparatus for efficient encoding of linear block codes uses a lookup table including a set of impulse responses to support faster performance by encoding in parallel. Advantages include a scalability that is lacking in existing schemes.

Claims

1. A method comprising:

receiving an information signal, said information signal comprising a string of k bits that includes p bits having nonzero values, k and p being integers;

receiving p impulse responses, each among said p impulse responses corresponding to one among said p bits; and

obtaining a checksum, said checksum comprising a summation of said p impulse responses.

2. The method according to claim 1, wherein each among said p impulse responses represents a response of an encoder for a linear block code to a string of k bits, said string including (k−

1) zero bits and a nonzero bit at a p-th position.

3. The method according to claim 2, wherein said checksum comprises a string of (n−

k) bits, n being an integer, and

wherein the linear block code is characterized by a generator polynomial of the form $G<br><br>\left(X\right)=1+\left(\underset{i=1}{\overset{n-k-1}{\sum <br><br>}}<br><br>\text{\hspace{1em}<br><br>}<br><br>g_i<br><br>X^i\right)+X^{n-k}.$

4. The method according to claim 1, wherein said checksum comprises a summation modulo 2 of said p impulse responses.

5. A method comprising:

receiving an information signal, said information signal comprising a string of k bits that includes p bits having nonzero values, k and p being integers;

receiving p impulse responses, each among said p impulse responses corresponding to one among said p bits;

receiving an encoder state signal, said encoder state signal comprising a string of (n−

k) bits that includes r bits having nonzero values, n and r being integers;

receiving r zero responses, each among said r zero responses corresponding to one among said r bits; and

obtaining a checksum, said checksum being a summation of said p impulse responses and said r zero responses.

6. The method according to claim 5, wherein each among said p impulse responses represents a response of an encoder for a linear block code to a string of k bits, said string including (k−

1) zero bits and a nonzero bit at a p-th position.

7. The method according to claim 6, wherein the linear block code is characterized by a generator polynomial of the form $G$

(X)=1+(∑

i=1n-k-1

 



gi

Xi)+Xn-k.

8. The method according to claim 5, wherein said checksum comprises a summation modulo 2 of said p impulse responses and said r zero responses.

9. The method according to claim 5, wherein each among said r zero responses represents a response of an encoder for a linear block code having an r-th component initial state to a string of k zero bits,

wherein said r-th component initial state is a string of length (n− k) including (n−

k−

1) zero bits and a nonzero bit at an r-th position.

10. The method according to claim 9, wherein the linear block code is characterized by a generator polynomial of the form $G$

(X)=1+(∑

i=1n-k-1

 



gi

Xi)+Xn-k.

11. A method comprising:

receiving a signal for encoding;

receiving a plurality of impulse responses;

receiving a plurality of zero responses; and

obtaining a checksum,

wherein said checksum comprises a summation of at least two responses, and

wherein each among said at least two responses is a member of one among said plurality of impulse responses and said plurality of zero responses, and

wherein each among said at least two responses corresponds to a predetermined position within said signal for encoding.

12. A method according to claim 11, wherein each among said at least two responses corresponds to a position within said signal for encoding that is occupied by a bit having a nonzero value.

13. The method according to claim 11, wherein said checksum comprises a summation modulo 2.

14. A method comprising:

receiving a first information signal, said first information signal comprising a string of k bits that includes p bits having nonzero values, k and p being integers;

receiving p impulse responses, each among said p impulse responses corresponding to one among said p bits;

receiving a first encoder state signal, said first encoder state signal comprising a string of (n−

k) bits that includes r bits having nonzero values, n and r being integers;

receiving r zero responses, each among said r zero responses corresponding to one among said r bits;

obtaining a second encoder state signal, said second encoder state signal comprising a summation of said p impulse responses and said r zero responses;

receiving a second information signal, said second information signal comprising a string of k bits; and

obtaining a checksum, said checksum being based at least in part on said second encoder state signal and said second information signal.

15. The method according to claim 14, wherein each among said p impulse responses represents a response of an encoder for a linear block code to a string of k bits, said string including (k−

1) zero bits and a nonzero bit at a p-th position.

16. The method according to claim 15, wherein the linear block code is characterized by a generator polynomial of the form $G$

(X)=1+(∑

i=1n-k-1

 



gi

Xi)+Xn-k.

17. The method according to claim 14, wherein each among said r zero responses represents a response of an encoder for a linear block code having an r-th component initial state to a string of k zero bits,

wherein said r-th component initial state is a string of length (n− k) including (n−

k−

1) zero bits and a nonzero bit at an r-th position.

18. The method according to claim 17, wherein the linear block code is characterized by a generator polynomial of the form $G$

(X)=1+(∑

i=1n-k-1

 



gi

Xi)+Xn-k.

19. A method comprising:

receiving a first information signal, said first information signal comprising a string of k bits that includes p bits having nonzero values, k and p being integers;

receiving p impulse responses, each among said p impulse responses corresponding to one among said p bits;

receiving a first encoder state signal, said first encoder state signal comprising a string of (n−

k) bits that includes r bits having nonzero values, n and r being integers;

receiving r zero responses, each among said r zero responses corresponding to one among said r bits;

obtaining a second encoder state signal, said second encoder state signal being a summation of said p impulse responses and said r zero responses and comprising a string of (n−

k) bits that includes s bits having nonzero values;

receiving a second information signal, said second information signal comprising a string of k bits that includes q bits having nonzero values;

receiving q impulse responses, each among said q impulse responses corresponding to one among said q bits;

receiving s zero responses, each among said s zero responses corresponding to one among said s bits; and

obtaining a checksum, said checksum being a summation of said q impulse responses and said s zero responses.

20. The method according to claim 19, wherein each among said p impulse responses represents a response of an encoder for a linear block code to a string of k bits, said string including (k−

1) zero bits and a nonzero bit at a p-th position.

21. The method according to claim 20, wherein the linear block code is characterized by a generator polynomial of the form $G$

(X)=1+(∑

i=1n-k-1

 



gi

Xi)+Xn-k.

22. The method according to claim 19, wherein said checksum comprises a summation modulo 2 of said q impulse responses and said s zero responses.

23. The method according to claim 19, wherein each among said r zero responses represents a response of an encoder for a linear block code having an r-th component initial state to a string of k zero bits,

wherein said r-th component initial state is a string of length (n− k) including (n−

k−

1) zero bits and a nonzero bit at an r-th position.

24. The method according to claim 23, wherein the linear block code is characterized by a generator polynomial of the form $G$

(X)=1+(∑

i=1n-k-1

 



gi

Xi)+Xn-k.

25. A method comprising:

receiving an information signal, said information signal comprising a string of k bits that includes p bits having nonzero values, k and p being integers;

receiving k impulse responses, each among said k impulse responses corresponding to one among said k bits; and

obtaining a checksum, said checksum comprising a summation of p among said k impulse responses.

26. The method according to claim 25, wherein each among said k impulse responses represents a response of an encoder for a linear block code to a string of k bits, said string including (k−

1) zero bits and a nonzero bit.

27. The method according to claim 26, wherein the linear block code is characterized by a generator polynomial of the form $G$

(X)=1+(∑

i=1n-k-1

 



gi

Xi)+Xn-k.

28. The method according to claim 25, wherein said checksum comprises a summation modulo 2 of said p impulse responses.

29. An apparatus comprising:

a logic matrix configured and arranged to receive an information signal and to output a checksum; and

a lookup table configured and arranged to store a plurality of responses of an encoder for a linear block code,

wherein each among said plurality of responses comprises a response of the encoder to a predetermined input string, and

wherein said checksum comprises a summation of at least two among said plurality of responses, and

wherein said at least two among said plurality of responses are selected at least in part on the basis of at least a portion of said information signal.

30. The apparatus according to claim 29, wherein said information signal comprises a string of k bits, k being an integer, and

wherein said plurality of responses includes k impulse responses, each among said k impulse responses corresponding to a position within said information signal.

31. The apparatus according to claim 30, wherein each among said k impulse responses comprises a response of the encoder having a zero initial state to a string of k bits,

wherein said string of k bits includes a bit of nonzero value at a position corresponding to the position within said information signal and (k−

1) bits of zero value.

32. The apparatus according to claim 29, wherein said logic matrix is further configured and arranged to receive an encoder state signal, and

wherein said at least two among said plurality of responses are selected at least in part on the basis of at least a portion of said encoder state signal.

33. The apparatus according to claim 32, wherein said encoder state signal comprises a string of (n−

k) bits, n being an integer, and

wherein said plurality of responses includes (n−

k) zero responses, each among said (n−

k) zero responses corresponding to a position within said encoder state signal.

34. The apparatus according to claim 33, wherein each among said (n−

k) zero responses comprises a response of the encoder having a component initial state to a string of k bits having zero values,

wherein said component initial state is a string of bits including a bit having a nonzero value at a position corresponding to the position within said encoder state signal and (k−

1) bits having zero values.