Error correcting method and apparatus for N:N+1 channel codes
First Claim
1. A method for correcting an error in N:
- N+1 channel codes, comprising the steps of;
(a) categorizing 2N codeword (N+1)-tuples among 2N+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 NG codeword (N+1)-tuples, NG being a positive integer, and the total number of codeword (N+1)-tuples in the M subsets is 2N given as follows;
wherein every codeword (N+1)-tuple in said each subset G has a predetermined number KG of lower bits and a predetermined number (N+1−
KG) 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 2N message N-tuples with said 2N 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.
5 Assignments
0 Petitions
Accused Products
Abstract
A method for correcting an error in N:N+1 channel codes categorizes 2N+1 codeword (N+1)-tuples into M subsets of codeword (N+1)-tuples, wherein each subset G has NG codeword (N+1)-tuples and the total number of codeword (N+1)-tuples in the M subsets is 2N and wherein each subset G has a predetermined number KG of lower bits and a predetermined number (N+1−KG) 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 2N message N-tuples are mapped with said 2N codeword (N+1)-tuples in the M subsets, respectively, in one-to-one correspondence to generate a lookup table.
-
Citations
18 Claims
-
1. A method for correcting an error in N:
- N+1 channel codes, comprising the steps of;
(a) categorizing 2N codeword (N+1)-tuples among 2N+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 NG codeword (N+1)-tuples, NG being a positive integer, and the total number of codeword (N+1)-tuples in the M subsets is 2N given as follows;
wherein every codeword (N+1)-tuple in said each subset G has a predetermined number KG of lower bits and a predetermined number (N+1−
KG) 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 2N message N-tuples with said 2N 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.- View Dependent Claims (2, 3, 4, 5, 6, 7, 8, 9)
(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.
- N+1 channel codes, comprising the steps of;
-
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 Log2M and the least number L by 1 and performing steps (g23) to (g26) until Log2M 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 KG of lower decimals in the transmitted codeword (N+1)-tuple into the lower bit and a predetermined number (N+1−
KG) 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 ┌
- Log2M┐
, wherein ┌
Log2M┐
is a smallest integer that is not smaller than Log2M.
- Log2M┐
-
7. The method of claim 1, wherein NG is equal to 2N+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.
- Q)-tuple is replaced with its corresponding parity codeword (P−
-
10. An apparatus for correcting an error in N:
- N+1 channel codes, comprising;
means for categorizing 2N codeword (N+1)-tuples among 2N−
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 NG codeword (N+1)-tuples, NG being a positive integer, and the total number of codeword (N+1)-tuples in the M subsets is 2N given as follows;
wherein every codeword (N+1)-tuple in said each subset G has a predetermined number KG of lower bits and a predetermined number (N+1−
KG) 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 2N message N-tuples with said 2N 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.- View Dependent Claims (11, 12, 13, 14, 15, 16, 17, 18)
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.
- N+1 channel codes, comprising;
-
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 Log2M and the least number L by 1 until Log2M 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 KG of lower decimals in the transmitted codeword (N+1)-tuple into the lower bit and a predetermined number (N+1−
KG) 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 ┌
- Log2M┐
, wherein ┌
Log2M┐
is a smallest integer that is not smaller than Log2M.
- Log2M┐
-
16. The apparatus of claim 10, wherein NG is equal to 2N+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.
- Q)-tuple is replaced with its corresponding parity codeword (P−
Specification