Error correcting method and apparatus for N:N+1 channel codes

• US 6,745,366 B1
• Filed: 11/21/2000
• Issued: 06/01/2004
• Est. Priority Date: 11/21/2000
• Status: Expired due to Fees

• Current Assignee: Wi-LAN Inc.
• Original Assignee: Dongbu Daewoo Electronics Corporation
• Inventors: Roh, Jae-Woo, Kang, Byung-Bok
• Primary Examiner(s): Lamarre, Guy J.
• Application Number:
  US09/717,950
• Time in Patent Office: 1,288 Days
• Field of Search: 714/800, 714/761-762, 714/805, 714/777, 714/769, 341/106, 341/65, 341/62, 375/341
• US Class Current: 714/805
• CPC Class Codes: H03M 13/03 Error detection or forward error correction by redundancy in data representation, i.e. code words containing more digits than the source words

Abstract

A method for correcting an error in N:N+1 channel codes categorizes 2^N+1 codeword (N+1)-tuples into M subsets of codeword (N+1)-tuples, wherein each subset G has N_G codeword (N+1)-tuples and the total number of codeword (N+1)-tuples in the M subsets is ₂^N and wherein each subset G has a predetermined number K_G of lower bits and a predetermined number (N+1−K_G) of higher bits and the number of lower bits in every codeword (N+1)-tuple in any subset is not equivalent to that of lower bits in every codeword (N+1)-tuple in any other subset. The 2^N message N-tuples are mapped with said 2^N codeword (N+1)-tuples in the M subsets, respectively, in one-to-one correspondence to generate a lookup table.

Claims

1. A method for correcting an error in N:

N+1 channel codes, comprising the steps of;

(a) categorizing 2^N codeword (N+1)-tuples among 2^N+1 codeword (N+1)-tuples into M subsets of codeword (N+1)-tuples, wherein M is an integer larger than 1, each subset G has N_G codeword (N+1)-tuples, N_G being a positive integer, and the total number of codeword (N+1)-tuples in the M subsets is 2_N given as follows;

$\underset{G=1}{\overset{M}{\sum <br><br>}}<br><br>\text{\hspace{1em}<br><br>}<br><br>N_G<br><br>2^N,$

 

wherein every codeword (N+1)-tuple in said each subset G has a predetermined number K_G of lower bits and a predetermined number (N+1−

K_G) of higher bits and the number of lower bits in every codeword (N+1)-tuple in any subset is not equivalent to that of lower bits in every codeword (N+1)-tuple in any other subset;

(b) matching 2^N message N-tuples with said 2^N codeword (N+1)-tuples in said M subsets, respectively, in one-to-one correspondence to generate a lookup table;

(c) dividing an input message into a plurality of message N-tuples;

(d) encoding each message N-tuple with its corresponding codeword (N+1)-tuple based on the lookup table sequentially;

(e) assigning a subset parity (P−

Q)-tuple to Q codeword (N+1)-tuples, wherein the subset parity (P−

Q)-tuple is redundant bits for representing subset information of said Q codeword (N+1)-tuples and P is larger than Q, P and Q being positive integers; and

(f) transmitting the Q codeword (N+1)-tuples and the subset parity (P−

Q)-tuple.

2. The method of claim 1, further comprising the step of:

(g) decoding the Q transmitted codeword (N+1)-tuples to reconstruct their corresponding Q reconstructed message N-tuples based on the lookup table and a transmitted subset parity (P−

Q)-tuple.

3. The method of claim 2, wherein the step (g) includes the steps of:

(g1) receiving the Q transmitted codeword (N+1)-tuples and the transmitted subset parity (P−

Q)-tuple;

(g2) evaluating at least one dispersion for each transmitted codeword (N+1)-tuple;

(g3) determining which subset G corresponds to said each transmitted codeword (N+1)-tuple based on the dispersion evaluation result to generate subset information Q-tuple for the Q transmitted codeword (N+1)-tuples;

(g4) modifying the subset information Q-tuple based on the transmitted subset parity (P−

Q)-tuple;

(g5) generating Q reconstructed codeword (N+1)-tuples based on the modified subset information Q-tuple; and

(g6) assigning to said Q reconstructed codeword (N+1)-tuples Q reconstructed message N-tuples based on the lookup table.

4. The method of claim 3, wherein the step (g2) has the step of:

(g21) receiving each transmitted codeword (N+1)-tuple as (N+1) decimals;

(g22) calculating a least number L of higher and lower bits in said M subsets of codeword (N+1)-tuples, L being an integer;

(g23) computing a greatest number K from the least number L and the subset number M, K being an integer;

(g24) deleting maximum or minimum decimals as many as the greatest number K in the (N+1) decimals to obtain (N+1−

K) decimals;

(g25) estimating an (N+1−

K)th dispersion for the (N+1−

K) decimals;

(g26) comparing the (N+1−

K)th dispersion with an (N+1−

K)th average dispersion which is an average of (N+1−

K)th dispersions for the plurality of transmitted codeword (N+1)-tuples; and

(g27) decreasing Log₂M and the least number L by 1 and performing steps (g23) to (g26) until Log₂M is equal to or smaller than 0 or the least number L is smaller than 0.

5. The method of claim 2, wherein the step (g5) has the step of:

(g51) converting, if a transmitted codeword (N+1)-tuple belongs to a subset G, a predetermined number K_G of lower decimals in the transmitted codeword (N+1)-tuple into the lower bit and a predetermined number (N+1−

K_G) of higher decimals into the higher bit to generate a reconstructed codeword (N+1)-tuple.

6. The method of claim 4, wherein the greatest number K is a maximum value of the least number L and ┌

Log₂M┐

, wherein ┌

Log₂M┐

is a smallest integer that is not smaller than Log₂M.

7. The method of claim 1, wherein N_G is equal to 2^N+1/M.

8. The method of claim 3, wherein N is equal to (P−

Q).

9. The method of claim 3, wherein said subset parity (P−

Q)-tuple is replaced with its corresponding parity codeword (P−

Q+1)-tuple based on the lookup table and said transmitted subset parity (P−

Q)-tuple is replaced with its corresponding transmitted parity codeword (P−

Q+1)-tuple.

10. An apparatus for correcting an error in N:

N+1 channel codes, comprising;

means for categorizing 2^N codeword (N+1)-tuples among 2<sup>N−

1</sup> codeword (N+1)-tuples into M subsets of codeword (N+1)-tuples, wherein M is an integer larger than 1, each subset G has N_G codeword (N+1)-tuples, N_G being a positive integer, and the total number of codeword (N+1)-tuples in the M subsets is 2^N given as follows;

$\underset{G=1}{\overset{M}{\sum <br><br>}}<br><br>\text{\hspace{1em}<br><br>}<br><br>N_G=2^N,$

 

wherein every codeword (N+1)-tuple in said each subset G has a predetermined number K_G of lower bits and a predetermined number (N+1−

K_G) of higher bits and the number of lower bits in every codeword (N+1)-tuple in any subset is not equivalent to that of lower bits in every codeword (N+1)-tupIe in any other subset;

means for matching 2^N message N-tuples with said 2^N codeword (N+1)-tuples in said M subsets, respectively, in one-to-one correspondence to generate a lookup table;

means for dividing an input message into a plurality of message N-tuples;

means for encoding each message N-tuple with its corresponding codeword (N+1)-tuple based on the lookup table sequentially;

means for assigning a subset parity (P−

Q)-tuple to Q codeword (N+1)-tuples, wherein the subset parity (P−

Q)-tuple is redundant bits for representing subset information of the Q codeword (N+1)-tuples and P is larger than Q, P and Q being positive integers; and

means for transmitting the Q codeword (N+1)-tuples and the subset parity (P−

Q)-tuple.

11. The apparatus of claim 10, further comprising:

mean for decoding the Q transmitted codeword (N+1)-tuples to reconstruct their corresponding Q reconstructed message N-tuples based on the lookup table and a transmitted subset parity (P−

Q)-tuple.

12. The apparatus of claim 11, wherein the decoding means includes:

means for receiving the Q transmitted codeword (N+1)-tuples and the transmitted subset parity (P−

Q)-tuple;

means for evaluating at least one dispersion for each transmitted codeword (N+1)-tuple;

means for determining which subset G corresponds to said each transmitted codeword (N+1)-tuple based on the dispersion evaluation result to generate subset information Q-tuple for the Q transmitted codeword (N+1)-tuples;

means for modifying the subset information Q-tuple based on the transmitted subset parity (P−

Q)-tuple;

means for generating Q reconstructed codeword (N+1)-tuples based on the modified subset information Q-tuple; and

means for assigning to said Q reconstructed codeword (N+1)-tuples Q reconstructed message N-tuples based on the lookup table.

13. The apparatus of claim 12, wherein the evaluation means has:

means for receiving each transmitted codeword (N+1)-tuple as (N+1) decimals;

means for calculating a least number L of higher and lower bits in said M subsets of codeword (N+1)-tuples, L being an integer;

means for computing a greatest number K from the least number L and the subset number M, K being an integer;

means for deleting maximum or minimum decimals as many as the greatest number K in the (N+1) decimals to obtain (N+1−

K) decimals;

means for estimating an (N+1−

K)th dispersion for the (N+1−

K) decimals;

means for comparing the (N+1−

K)th dispersion with an (N+1−

K)th average dispersion which is an average of (N+1−

K)th dispersions for the plurality of transmitted codeword (N+1)-tuples; and

means for decreasing Log₂M and the least number L by 1 until Log₂M is equal to or smaller than 0 or the least number L is smaller than 0.

14. The apparatus of claim 13, wherein the generation means has:

means for converting, if a transmitted codeword (N+1)-tuple belongs to a subset G, a predetermined number K_G of lower decimals in the transmitted codeword (N+1)-tuple into the lower bit and a predetermined number (N+1−

K_G) of higher decimals into the higher bit to generate a reconstructed codeword (N+1)-tuple.

15. The apparatus of claim 13, wherein the greatest number K is a maximum value of the least number L and ┌

Log₂M┐

, wherein ┌

Log₂M┐

is a smallest integer that is not smaller than Log₂M.

16. The apparatus of claim 10, wherein N_G is equal to 2^N+1/M.

17. The apparatus of claim 12, wherein N is equal to (P−

Q).

18. The apparatus of claim 12, wherein said subset parity (P−

Q)-tuple is replaced with its corresponding parity codeword (P−

Q+1)-tuple based on the lookup table and said transmitted subset parity (P−

Q)-tuple is replaced with its corresponding transmitted parity codeword (P−

Q+1)-tuple.