US5481566A
Expired / Lapsed
US
⏱️ 0.0 years remaining
Method and apparatus to increase efficiency of systematic codes
Assignee: AT&T Inc
•
Filing: 1993-12-29
•
Granted: 1996-01-02
•
Expires: 2013-12-29
Abstract
Abstract A method and apparatus for increasing the coding efficiency of a digital data transmission system from k/n to (k+1)/n by truncating a check bit from a generated checkword and adding an extra information bit prior to transmission. The encoding algorithm at the receiver borrows the added information bit to replace the truncated check bit in order to perform error detection and correction n the entire codeword. If an error is detected at the shared bit position, the shared bit is not corrected by the decoding circuit since a detected error in that position is more likely a result of bit inversion due to replacement than due to a transmission fault. The coding efficiency of the transmission system is increased from k/n to (k+1)/n while the number of bit errors correctable by the system is only reduced to, on the average, t-(1/2) for some range of BER's.
Inventors
- 👤 Anthony G. Kulesa
Bibliographic Details
Application Number
—
Jurisdiction
US
Data Source
google_patents
Last Synchronized
2026-10-28 10:37
CPC Classifications
H; H03; H03M; H03M13/00
Claims Analysis
Total Claims: 16
Claim 1
Independent Claim
240 words
In a digital data transmission system implementing a predefined systematic coding algorithm to encode blocks of information bits into codewords prior to transmission, wherein each of said codewords has a fixed number of bits n comprising a fixed number of information bits k concatenated with a fixed number of check bits r such that n=k+r, and wherein said transmission system implements after transmission of said codewords a predefined decoding algorithm corresponding to said encoding algorithm and capable of detecting and correcting for each of said codewords t errors introduced during transmission, wherein said coding algorithm has a coding efficiency of k/n; a method for increasing the coding efficiency of the system without changing the fixed codeword length n, said method comprising the steps of: (a) generating a checkword having r check bits, wherein r is greater than 1, from the systematic coding algorithm using an information word having k information bits as its input; (b) truncating one bit R(lost) of said checkword to form a modified checkword having r-1 check bits; (c) forming a codeword having n bits by concatenating said information word with an additional information bit K(added) and said modified checkword; (d) transmitting said codeword to a receiver; (e) borrowing said additional information bit K(added) to replace said truncated check bit R(lost) in the decoding algorithm; and (f) decoding said codeword utilizing the predefined decoding algorithm; whereby the coding efficiency of the transmission system is increased to (k+1)/n.
Claim 2
Dependent Claim
240 words
In a digital data transmission system implementing a predefined systematic coding algorithm to encode blocks of information bits into codewords prior to transmission, wherein each of said codewords has a fixed number of bits n comprising a fixed number of information bits k concatenated with a fixed number of check bits r such that n=k+r, and wherein said transmission system implements after transmission of said codewords a predefined decoding algorithm corresponding to said encoding algorithm and capable of detecting and correcting for each of said codewords t errors introduced during transmission, wherein said coding algorithm has a coding efficiency of k/n; a method for increasing the coding efficiency of the system without changing the fixed codeword length n, said method comprising the steps of: (a) generating a checkword having r check bits, wherein r is greater than 1, from the systematic coding algorithm using an information word having k information bits as its input; (b) truncating one bit R(lost) of said checkword to form a modified checkword having r-1 check bits; (c) forming a codeword having n bits by concatenating said information word with an additional information bit K(added) and said modified checkword; (d) transmitting said codeword to a receiver; (e) borrowing said additional information bit K(added) to replace said truncated check bit R(lost) in the decoding algorithm; and (f) decoding said codeword utilizing the predefined decoding algorithm; whereby the coding efficiency of the transmission system is increased to (k+1)/n.
Claim 3
Dependent Claim
27 words
The method of claim 1 further comprising the step of disabling correction of the additional information bit K(added) in the error correction portion of the decoding algorithm.
Claim 4
Dependent Claim
39 words
The method of claim 1 in which steps (a) through (f) are performed for p codewords out of a total sequence of q codewords; whereby the number of bit errors that can be corrected by the system is t-(p/2q).
Claim 5
Dependent Claim
34 words
The method of claim 1 in which steps (a) through (f) are performed for every codeword in a sequence; whereby the number of bit errors that can be corrected by the system is t-(1/2).
Claim 6
Dependent Claim
243 words
In a digital data transmission system implementing a predefined systematic coding algorithm to encode blocks of information bits into codewords prior to transmission, wherein each of said codewords has a fixed number of bits n comprising a fixed number of information bits k concatenated with a fixed number of check bits r such that n=k+r, and wherein said transmission system implements after transmission of said codewords a predefined decoding algorithm corresponding to said encoding algorithm and capable of detecting and correcting for each of said codewords t errors introduced during transmission, wherein said coding algorithm has a coding efficiency of k/n; a method for increasing the coding efficiency of the system without changing the fixed codeword length n, said method comprising the steps of: (a) generating a checkword having r check bits, wherein r is greater than 1, from the systematic coding algorithm using an information word having k information bits as its input; (b) truncating m bits of said checkword, wherein m is less than r, to form a modified checkword having r-m check bits; (c) forming a codeword having n bits by concatenating said information word with m additional information bits and said modified checkword; (d) transmitting said codeword to a receiver; (e) borrowing said m additional information bits to replace said truncated check bits in the decoding algorithm; and (f) decoding said codeword utilizing the predefined decoding algorithm; whereby the coding efficiency of the transmission system is increased to (k+m)/n.
Claim 7
Dependent Claim
243 words
In a digital data transmission system implementing a predefined systematic coding algorithm to encode blocks of information bits into codewords prior to transmission, wherein each of said codewords has a fixed number of bits n comprising a fixed number of information bits k concatenated with a fixed number of check bits r such that n=k+r, and wherein said transmission system implements after transmission of said codewords a predefined decoding algorithm corresponding to said encoding algorithm and capable of detecting and correcting for each of said codewords t errors introduced during transmission, wherein said coding algorithm has a coding efficiency of k/n; a method for increasing the coding efficiency of the system without changing the fixed codeword length n, said method comprising the steps of: (a) generating a checkword having r check bits, wherein r is greater than 1, from the systematic coding algorithm using an information word having k information bits as its input; (b) truncating m bits of said checkword, wherein m is less than r, to form a modified checkword having r-m check bits; (c) forming a codeword having n bits by concatenating said information word with m additional information bits and said modified checkword; (d) transmitting said codeword to a receiver; (e) borrowing said m additional information bits to replace said truncated check bits in the decoding algorithm; and (f) decoding said codeword utilizing the predefined decoding algorithm; whereby the coding efficiency of the transmission system is increased to (k+m)/n.
Claim 8
Dependent Claim
27 words
The method of claim 5 further comprising the step of disabling correction of the m additional information bits in the error correction portion of the decoding algorithm.
Claim 9
Dependent Claim
41 words
The method of claim 5 in which steps (a) through (f) are performed for p codewords out of a total sequence of q codewords; whereby the number of bit errors that can be corrected by the system is t-(p/2 m q).
Claim 10
Dependent Claim
36 words
The method of claim 5 in which steps (a) through (f) are performed for every codeword in a sequence; whereby the number of bit errors that can be corrected by the system is t-(1/2 m ).
Claim 11
Dependent Claim
203 words
A digital data transmission system comprising (a) encoding means for implementing a predefined systematic coding algorithm to encode blocks of information bits into codewords prior to transmission, wherein each of said codewords comprises an information word having a fixed number of information bits k concatenated with a checkword having a fixed number of check bits r thereby forming a codeword having a fixed number of bits n such that n=k+r; (b) means to truncate one check bit R(lost) from said checkword to form a modified checkword having r-1 check bits; (c) means to concatenate said information word with an additional information bit K(added) and said modified checkword to form an n-bit codeword; (d) means for transmitting said codeword over a communications channel; (e) means to receive said codeword from said communications channel; and (f) decoding means for implementing after reception of said codewords a predefined decoding algorithm corresponding to said encoding algorithm and capable of detecting and correcting for each of said codewords t errors introduced during transmission; said decoding means being capable of borrowing said additional information bit K(added) to replace said truncated check bit R(lost) in the decoding algorithm; whereby the coding efficiency of the transmission system is increased to (k+1)/n.
Claim 12
Dependent Claim
203 words
A digital data transmission system comprising (a) encoding means for implementing a predefined systematic coding algorithm to encode blocks of information bits into codewords prior to transmission, wherein each of said codewords comprises an information word having a fixed number of information bits k concatenated with a checkword having a fixed number of check bits r thereby forming a codeword having a fixed number of bits n such that n=k+r; (b) means to truncate one check bit R(lost) from said checkword to form a modified checkword having r-1 check bits; (c) means to concatenate said information word with an additional information bit K(added) and said modified checkword to form an n-bit codeword; (d) means for transmitting said codeword over a communications channel; (e) means to receive said codeword from said communications channel; and (f) decoding means for implementing after reception of said codewords a predefined decoding algorithm corresponding to said encoding algorithm and capable of detecting and correcting for each of said codewords t errors introduced during transmission; said decoding means being capable of borrowing said additional information bit K(added) to replace said truncated check bit R(lost) in the decoding algorithm; whereby the coding efficiency of the transmission system is increased to (k+1)/n.
Claim 13
Dependent Claim
32 words
The digital data transmission system of claim 9 further comprising: (g) gating means to selectively disable correction of the additional information bit K(added) in the error correction portion of the decoding algorithm.
Claim 14
Dependent Claim
16 words
The digital data transmission system of claim 10 wherein said gating means is an AND gate.
Claim 15
Dependent Claim
344 words
A digital data transmission system comprising: (a) a BCH (15, 7) encoder which generates a 15-bit codeword in the form (m 8 m 7 m 6 m 5 m 4 m 3 m 2 c 8 c 7 c 6 c 5 c 4 c 3 c 2 c 1 ), wherein (m 8 m 7 m 6 m 5 m 4 m 3 m 2 ) represents the first seven bits of an eight bit information word desired to be transmitted and (c 8 c 7 c 6 c 5 c 4 c 3 c 2 c 1 ) represents an 8-bit checkword generated by said BCH (15, 7) encoder as a result of inputting said seven information bits (m 8 m 7 m 6 m 5 m 4 m 3 m 2 ); (b) means to truncate (c 8 ) and add in its place the information bit (m 1 ) and thus provide a modified 15-bit codeword (m 8 m 7 m 6 m 5 m 4 m 3 m 2 m 1 c 7 c 6 c 5 c 4 c 3 c 2 c 1 ); (c) means for transmitting said modified codeword (m 8 m 7 m 6 m 5 m 4 m 3 m 2 m 1 c 7 c 6 c 5 c 4 c 3 c 2 c 1 ) over a communications channel; (d) means to receive said modified codeword (m 8 m 7 m 6 m 5 m 4 m 3 m 2 m 1 c 7 c 6 c 5 c 4 c 3 c 2 c 1 ) from said communications channel; and (e) a BCH (15, 7+1) decoder comprising a BCH (15, 7) decoder modified so that the (m 1 ) bit is also used as (c 8 ) in a decoding algorithm and further modified so that the correction for the (m 1 /c 8 ) bit is gated out by a selective control signal as desired; whereby the coding efficiency of the transmission system is increased to 8/15.
Claim 16
Dependent Claim
344 words
A digital data transmission system comprising: (a) a BCH (15, 7) encoder which generates a 15-bit codeword in the form (m 8 m 7 m 6 m 5 m 4 m 3 m 2 c 8 c 7 c 6 c 5 c 4 c 3 c 2 c 1 ), wherein (m 8 m 7 m 6 m 5 m 4 m 3 m 2 ) represents the first seven bits of an eight bit information word desired to be transmitted and (c 8 c 7 c 6 c 5 c 4 c 3 c 2 c 1 ) represents an 8-bit checkword generated by said BCH (15, 7) encoder as a result of inputting said seven information bits (m 8 m 7 m 6 m 5 m 4 m 3 m 2 ); (b) means to truncate (c 8 ) and add in its place the information bit (m 1 ) and thus provide a modified 15-bit codeword (m 8 m 7 m 6 m 5 m 4 m 3 m 2 m 1 c 7 c 6 c 5 c 4 c 3 c 2 c 1 ); (c) means for transmitting said modified codeword (m 8 m 7 m 6 m 5 m 4 m 3 m 2 m 1 c 7 c 6 c 5 c 4 c 3 c 2 c 1 ) over a communications channel; (d) means to receive said modified codeword (m 8 m 7 m 6 m 5 m 4 m 3 m 2 m 1 c 7 c 6 c 5 c 4 c 3 c 2 c 1 ) from said communications channel; and (e) a BCH (15, 7+1) decoder comprising a BCH (15, 7) decoder modified so that the (m 1 ) bit is also used as (c 8 ) in a decoding algorithm and further modified so that the correction for the (m 1 /c 8 ) bit is gated out by a selective control signal as desired; whereby the coding efficiency of the transmission system is increased to 8/15.
References Cited (Backward Citations)
US3697949A
Cited
US4077028A
Cited
US4107650A
Cited
US4156867A
Cited
US4312069A
Cited
US4488302A
Cited
US4605921A
Cited
US4744086A
Cited
US4691319A
Cited
US4763331A
Cited
US4849976A
Cited
US4899340A
Cited
US5010554A
Cited
US5179560A
Cited
US5379305A
Cited
USPTO Annuity & Maintenance Windows
| Annuity Stage | Window Opens | Payment Deadline | Surcharge Period Until | Estimated Fee | Status |
|---|---|---|---|---|---|
| 3.5 Years (Year 4) | 1999-01-01 | 1999-07-03 | 2000-01-02 | $2000.00 | Window Closed / Lapsed |
| 7.5 Years (Year 8) | 2003-01-01 | 2003-07-03 | 2004-01-02 | $3760.00 | Window Closed / Lapsed |
| 11.5 Years (Year 12) | 2007-01-01 | 2007-07-03 | 2008-01-02 | $7700.00 | Window Closed / Lapsed |