Patent US6745366B1 successfully refreshed from Google Patents.
US6745366B1
Expired / Lapsed
US
⏱️ 0.0 years remaining
Error correcting method and apparatus for N:N+1 channel codes
Assignee: Quarterhill Inc
•
Filing: 2000-11-21
•
Granted: 2004-06-01
•
Expires: 2020-11-21
Abstract
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 2 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.
Inventors
- 👤 Jae-Woo Roh
- 👤 Byung-Bok Kang
Bibliographic Details
Application Number
—
Jurisdiction
US
Data Source
google_patents
Last Synchronized
2026-11-09 16:49
CPC Classifications
H; H03; H03M; H03M13/00; H03M13/03
Claims Analysis
Total Claims: 20
Claim 1
Independent Claim
243 words
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: ∑ G = 1 M 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)-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.
Claim 2
Independent Claim
243 words
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: ∑ G = 1 M 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)-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.
Claim 3
Dependent Claim
37 words
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.
Claim 4
Dependent Claim
111 words
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.
Claim 5
Dependent Claim
158 words
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 2 M and the least number L by 1 and performing steps (g23) to (g26) until Log 2 M is equal to or smaller than 0 or the least number L is smaller than 0.
Claim 6
Dependent Claim
63 words
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.
Claim 7
Dependent Claim
40 words
The method of claim 4 , wherein the greatest number K is a maximum value of the least number L and ┌Log 2 M┐, wherein ┌Log 2 M┐ is a smallest integer that is not smaller than Log 2 M.
Claim 8
Dependent Claim
15 words
The method of claim 1 , wherein N G is equal to 2 N+1 /M.
Claim 9
Dependent Claim
12 words
The method of claim 3 , wherein N is equal to (P−Q).
Claim 10
Dependent Claim
39 words
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.
Claim 11
Independent Claim
246 words
An apparatus for correcting an error in N:N+1 channel codes, comprising: means for 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: ∑ G = 1 M 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.
Claim 12
Independent Claim
246 words
An apparatus for correcting an error in N:N+1 channel codes, comprising: means for 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: ∑ G = 1 M 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.
Claim 13
Dependent Claim
35 words
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.
Claim 14
Dependent Claim
114 words
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.
Claim 15
Dependent Claim
156 words
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 2 M and the least number L by 1 until Log 2 M is equal to or smaller than 0 or the least number L is smaller than 0.
Claim 16
Dependent Claim
61 words
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.
Claim 17
Dependent Claim
40 words
The apparatus of claim 13 , wherein the greatest number K is a maximum value of the least number L and ┌Log 2 M┐, wherein ┌Log 2 M┐ is a smallest integer that is not smaller than Log 2 M.
Claim 18
Dependent Claim
15 words
The apparatus of claim 10 , wherein N G is equal to 2 N+1 /M.
Claim 19
Dependent Claim
12 words
The apparatus of claim 12 , wherein N is equal to (P−Q).
Claim 20
Dependent Claim
39 words
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.
References Cited (Backward Citations)
US5740203A
Cited
USPTO Annuity & Maintenance Windows
| Annuity Stage | Window Opens | Payment Deadline | Surcharge Period Until | Estimated Fee | Status |
|---|---|---|---|---|---|
| 3.5 Years (Year 4) | 2007-06-01 | 2007-12-01 | 2008-06-01 | $2000.00 | Window Closed / Lapsed |
| 7.5 Years (Year 8) | 2011-06-01 | 2011-12-01 | 2012-06-01 | $3760.00 | Window Closed / Lapsed |
| 11.5 Years (Year 12) | 2015-06-01 | 2015-12-01 | 2016-06-01 | $7700.00 | Window Closed / Lapsed |