US5285454A
Expired / Lapsed
US
⏱️ 0.0 years remaining
Method and apparatus for encoding and decoding unordered error correcting codes
Assignee: International Business Machines Corp
•
Filing: 1991-06-14
•
Granted: 1994-02-08
•
Expires: 2011-06-14
Abstract
Abstract An unordered error correcting code is constructed by an encoding method and apparatus that accepts k bits of information and is capable of providing unordered ECC codewords. All pairs of these codewords are at least a distance d apart, where d≧(2t+1) and t is the maximum number of errors correctable by the code. The k bits of information are encoded with an ECC encoding algorithm to produce ECC codewords that are at least distance d apart. The least number of tail bits required to produce the unordered ECC codewords is appended to each of the ECC codewords. The tail bits for each codeword are constructed by dividing its weight by d for determining the integer part of the resulting quotient, generating a binary representation of the value of its integer part, and complementing said binary representation. A noisy received version of the ECC codeword with tail bits truncated is decoded and a preselected error correcting algorithm is applied to correct t 1 actual errors and produce a decoded ECC codeword. Tail bits corresponding to the decoded ECC codeword are generated and compared with segregated tail bits for the noisy received ECC codeword for determining the number t 2 of errors actually detected. The k information bits derived from the decoded ECC codeword are outputted when (t 1 +t 2 )≦t.
Inventors
- 👤 Miguel M. Blaum
- 👤 Jehoshua Bruck
Bibliographic Details
Application Number
—
Jurisdiction
US
Data Source
google_patents
Last Synchronized
2026-11-08 06:52
CPC Classifications
H; H03; H03M; H03M13/00; H03M13/03; H03M13/05; H03M13/47; H03M13/51
Claims Analysis
Total Claims: 11
Claim 1
Independent Claim
170 words
A method of decoding unordered codewords of an unordered error correcting code, each of which comprises k information bits, n-k ECC bits, and unordering tail bits, each arbitrary pair of n bits being at least a distance d apart, where d≧(2t+1) and t is the maximum number of errors correctable by the code comprising the steps of: segregating the unordering tail bits to produce a noisy received version of an ECC codeword; decoding the noisy received version of the ECC codeword with the tail bits truncated and applying a preselected error correcting algorithm to correct t 1 actual errors and produce a decoded ECC codeword; generating a selected number of tail bits corresponding to the decoded ECC codeword; comparing the segregated tail bits for the noisy received ECC codeword with the generated tail bits for the decoded ECC codeword for determining the number t 2 of errors actually detected; and providing as an output the k information bits derived from the decoded ECC codeword when (t 1 +t 2 )≦t.
Claim 2
Independent Claim
170 words
A method of decoding unordered codewords of an unordered error correcting code, each of which comprises k information bits, n-k ECC bits, and unordering tail bits, each arbitrary pair of n bits being at least a distance d apart, where d≧(2t+1) and t is the maximum number of errors correctable by the code comprising the steps of: segregating the unordering tail bits to produce a noisy received version of an ECC codeword; decoding the noisy received version of the ECC codeword with the tail bits truncated and applying a preselected error correcting algorithm to correct t 1 actual errors and produce a decoded ECC codeword; generating a selected number of tail bits corresponding to the decoded ECC codeword; comparing the segregated tail bits for the noisy received ECC codeword with the generated tail bits for the decoded ECC codeword for determining the number t 2 of errors actually detected; and providing as an output the k information bits derived from the decoded ECC codeword when (t 1 +t 2 )≦t.
Claim 3
Dependent Claim
23 words
The method of claim 1, wherein said selected number is the least number of tail bits required to produce the unordered ECC codewords.
Claim 4
Dependent Claim
20 words
The method of claim 1, including the step of: activating an uncorrectable error-responsive protocol when (t 1 +t 2 )>t.
Claim 5
Independent Claim
96 words
An apparatus for constructing an unordered error correcting code (ECC) that accepts k bits of information, comprising: an encoder for encoding electrical signals representing the k bits of information with an ECC encoding algorithm to transform them into electrical signals constituting ECC codewords, each arbitrary pair of which is at least a distance d apart, where d≧(2t+1) and t is the maximum number of errors correctable by the code; and electrical circuitry for generating and appending to each of the ECC codewords a selected number of electrical signals constituting tail bits to produce unordered ECC codewords.
Claim 6
Independent Claim
96 words
An apparatus for constructing an unordered error correcting code (ECC) that accepts k bits of information, comprising: an encoder for encoding electrical signals representing the k bits of information with an ECC encoding algorithm to transform them into electrical signals constituting ECC codewords, each arbitrary pair of which is at least a distance d apart, where d≧(2t+1) and t is the maximum number of errors correctable by the code; and electrical circuitry for generating and appending to each of the ECC codewords a selected number of electrical signals constituting tail bits to produce unordered ECC codewords.
Claim 7
Dependent Claim
68 words
The apparatus of claim 4, wherein said circuitry comprises: a tail generating circuit for dividing the weight of each codeword by d to determine the integer part of the resulting quotient and generating a binary representation of the value of the integer part of each codeword; and a complementing circuit for complementing each such binary representation to provide the tail bits that are appended to the ECC codewords.
Claim 8
Dependent Claim
23 words
The apparatus of claim 4, wherein said selected number is the least number of tail bits required to produce the unordered ECC codewords.
Claim 9
Independent Claim
174 words
An apparatus for decoding unordered codewords of an unordered error correcting code, each of which comprises k information bits, n-k ECC bits, and unordering tail bits, each pair of n bits being at least a distance d apart, where d≧(2t+1) and t is the maximum number of errors correctable by the code comprising: means for segregating the unordering tail bits to produce a noisy received version of an ECC codeword; means for decoding the noisy received version of the ECC codeword with the tail bits truncated; means for applying a preselected error correcting algorithm to correct t 1 actual errors and produce a decoded ECC codeword; means for generating a selected number of tail bits corresponding to the decoded ECC codeword; means for comparing the segregated tail bits for the noisy received ECC codeword with the generated tail bits for the decoded ECC codeword for determining the number t 2 of errors actually detected; and means for outputting the k information bits derived from the decoded ECC codeword when (t 1 +t 2 )≧t.
Claim 10
Independent Claim
174 words
An apparatus for decoding unordered codewords of an unordered error correcting code, each of which comprises k information bits, n-k ECC bits, and unordering tail bits, each pair of n bits being at least a distance d apart, where d≧(2t+1) and t is the maximum number of errors correctable by the code comprising: means for segregating the unordering tail bits to produce a noisy received version of an ECC codeword; means for decoding the noisy received version of the ECC codeword with the tail bits truncated; means for applying a preselected error correcting algorithm to correct t 1 actual errors and produce a decoded ECC codeword; means for generating a selected number of tail bits corresponding to the decoded ECC codeword; means for comparing the segregated tail bits for the noisy received ECC codeword with the generated tail bits for the decoded ECC codeword for determining the number t 2 of errors actually detected; and means for outputting the k information bits derived from the decoded ECC codeword when (t 1 +t 2 )≧t.
Claim 11
Dependent Claim
19 words
The apparatus of claim 7, including means for initiating a desired control operation when (t 1 +t 2 )>t.
References Cited (Backward Citations)
USPTO Annuity & Maintenance Windows
| Annuity Stage | Window Opens | Payment Deadline | Surcharge Period Until | Estimated Fee | Status |
|---|---|---|---|---|---|
| 3.5 Years (Year 4) | 1997-02-07 | 1997-08-09 | 1998-02-08 | $2000.00 | Window Closed / Lapsed |
| 7.5 Years (Year 8) | 2001-02-07 | 2001-08-09 | 2002-02-08 | $3760.00 | Window Closed / Lapsed |
| 11.5 Years (Year 12) | 2005-02-07 | 2005-08-09 | 2006-02-08 | $7700.00 | Window Closed / Lapsed |