Patent US4295218A successfully refreshed from Google Patents.
US4295218A
Expired / Lapsed
US
⏱️ 0.0 years remaining
Error-correcting coding system
Assignee: Samsung Electronics Co Ltd
•
Filing: 1979-06-25
•
Granted: 1981-10-13
•
Expires: 1999-06-25
Abstract
Abstract A method and apparatus for constructing long error-correcting codes from one or more shorter error-correcting codes, referred to as subcodes, and a bipartite graph. The graph specifies carefully chosen subsets of the digits of the new codes that must be codewords in one of the shorter subcodes. Lower bounds on the rate and the minimum distance of the new code are derived in terms of the parameters of the graph and the subcodes. Both the encoders and decoders employed take advantage of the code's explicit decomposition into subcodes to decompose and simplify the associated computational processes. Bounds on the performance of two specific decoding algorithms are established, and the asymptotic growth of the complexity of decoding for two types of codes and decoders is analyzed. The decoders are able to make effective use of probabilistic information supplied by the channel receiver, such as reliability information, without greatly increasing the number of computations required. By a chosen transmission order for the digits that is appropriate for the graph and the subcodes, the code has excellent burst-error correction abilities.
Inventors
- 👤 Robert M. Tanner
Bibliographic Details
Application Number
—
Jurisdiction
US
Data Source
google_patents
Last Synchronized
2026-10-25 17:38
CPC Classifications
H; H03; H03M; H03M13/00; H03M13/03; H03M13/05; H03M13/11; H03M13/1102; H03M13/1105; H03M13/1111
Claims Analysis
Total Claims: 13
Claim 1
Independent Claim
366 words
In self-correcting date transmitting apparatus wherein a selected member of a family of codewords is transmitted, thereafter received in a modified state, and then interpreted at the receiving end as being the member closest in appearance to the modified codeword, the method of transmitting and correcting data comprising the steps of: (a) establishing the family of codewords by (a1) selecting a connected bipartite undirected graph having a plurality of first nodes and a plurality of second nodes connected together by a plurality of edges and wherein none of said first nodes are connected to another of said first nodes and none of said second nodes are connected to another of said second nodes; (a2) assigning a digit position for the codeword to each of said first nodes; (a3) assigning subcode definitions to be associated with each of said first nodes; (a4) assigning a set of values to be associated with selected ones of said second nodes such that as inputs to the ones of said first nodes connected to said selected ones of said second nodes said subcode definitions thereof are satisfied; (a5) establishing said set of values from step (a4) in the digit sequence assigned in step (a2) as a member of the family of codewords; and, (a6) repeating steps (a4) and (a5) for different sets of values until the desired number of members of the family have been established; (b) placing the digits of each codeword as received following transmission in individual storage registers connected as inputs to test nodes corresponding to said first nodes of said graphs; (c) testing the contents of said storage registers as inputs against said subcode definitions associated with said first node; (d) using the contents of said storage registers as the received codeword is all said subcode definitions are satisfied, otherwise continuing to step (e); (e) using the contents of said storage registers as the received codeword if a preselected number of corrective iterations have been tried, otherwise continuing to step (f); and, (f) modifying the contents of at least one of said storage registers which is connected as an input to one of said nodes which has its associated subcode definition unsatisfied and returning to step (c).
Claim 2
Dependent Claim
366 words
In self-correcting date transmitting apparatus wherein a selected member of a family of codewords is transmitted, thereafter received in a modified state, and then interpreted at the receiving end as being the member closest in appearance to the modified codeword, the method of transmitting and correcting data comprising the steps of: (a) establishing the family of codewords by (a1) selecting a connected bipartite undirected graph having a plurality of first nodes and a plurality of second nodes connected together by a plurality of edges and wherein none of said first nodes are connected to another of said first nodes and none of said second nodes are connected to another of said second nodes; (a2) assigning a digit position for the codeword to each of said first nodes; (a3) assigning subcode definitions to be associated with each of said first nodes; (a4) assigning a set of values to be associated with selected ones of said second nodes such that as inputs to the ones of said first nodes connected to said selected ones of said second nodes said subcode definitions thereof are satisfied; (a5) establishing said set of values from step (a4) in the digit sequence assigned in step (a2) as a member of the family of codewords; and, (a6) repeating steps (a4) and (a5) for different sets of values until the desired number of members of the family have been established; (b) placing the digits of each codeword as received following transmission in individual storage registers connected as inputs to test nodes corresponding to said first nodes of said graphs; (c) testing the contents of said storage registers as inputs against said subcode definitions associated with said first node; (d) using the contents of said storage registers as the received codeword is all said subcode definitions are satisfied, otherwise continuing to step (e); (e) using the contents of said storage registers as the received codeword if a preselected number of corrective iterations have been tried, otherwise continuing to step (f); and, (f) modifying the contents of at least one of said storage registers which is connected as an input to one of said nodes which has its associated subcode definition unsatisfied and returning to step (c).
Claim 3
Dependent Claim
12 words
The method of claim 1 wherein: p1 said subcode definitions are identical.
Claim 4
Dependent Claim
66 words
The method of claim 1 wherein: said selected graph is one wherein the girth is approximately twice the diameter where the "diameter" is the maximum of the minimum length path connecting said nodes taken in pairs and the "girth" is the length of the shortest possible path for starting at one of said nodes, visiting distinct ones of said nodes, and returning to said starting node.
Claim 5
Independent Claim
15 words
The method of caim 3 wherein: said selected graph has a girth greater than four.
Claim 6
Independent Claim
15 words
The method of caim 3 wherein: said selected graph has a girth greater than four.
Claim 7
Dependent Claim
56 words
The method of claim 1 wherein: (a) the digits as received and stored in said storage registers each have a probability figure associated therewith that the digit is the digit indicated; and, (b) said step (f) includes testing said probability figures and allowing the modification of only those digits having a probability below a preselected level.
Claim 8
Dependent Claim
59 words
The method of claim 1 wherein: (a) the digits as received and stored in said storage registers each have a probability figure associated therewith that the digit is the digit indicated; and, (b) said step (f) includes calculating and storing new ones of said probability figures as a function of said modifications made to reflect the new true probabilities.
Claim 9
Dependent Claim
162 words
In self-correcting data transmitting apparatus wherein a selected member of a family of codewords is transmitted, thereafter received in a modified state, and then interpreted at the receiving end as being the member closest in appearance to the modified codeword, the improvement comprising: (a) a plurality of storage registers for holding the digits of the codeword as received; and, (b) a plurality of test circuit means connected to each other and to selected ones of said storage registers for sensing the contents of said registers, for comparing said sensed contents as inputs with subcode definitions associated with each of said test circuit means and which subcode definitions are satisfied by all members of the family of codewords being transmitted, and for causing the contents of at least one of said storage registers connected to one of said test circuit means wherein said subcode definition is not satisfied to be changed to a value which more nearly compares to the compared subcode definition.
Claim 10
Dependent Claim
162 words
In self-correcting data transmitting apparatus wherein a selected member of a family of codewords is transmitted, thereafter received in a modified state, and then interpreted at the receiving end as being the member closest in appearance to the modified codeword, the improvement comprising: (a) a plurality of storage registers for holding the digits of the codeword as received; and, (b) a plurality of test circuit means connected to each other and to selected ones of said storage registers for sensing the contents of said registers, for comparing said sensed contents as inputs with subcode definitions associated with each of said test circuit means and which subcode definitions are satisfied by all members of the family of codewords being transmitted, and for causing the contents of at least one of said storage registers connected to one of said test circuit means wherein said subcode definition is not satisfied to be changed to a value which more nearly compares to the compared subcode definition.
Claim 11
Dependent Claim
23 words
The improvement to self-correcting data transmitting apparatus of claim 7 wherein: said plurality of test circuit means test for the same subcode definition.
Claim 12
Dependent Claim
65 words
The improvement to self-correcting data transmitting apparatus of claim 7 wherein said plurality of storage registers includes: (a) means for receiving and maintaining a probability figure associated with each received digit of the codeword that the digit is the digit indicated; and, (b) means for allowing only ones of said storage registers to be changed wherein the probability associated therewith is below a threshold amount.
Claim 13
Dependent Claim
76 words
The improvement to self-correcting data transmitting apparatus of claim 7 wherein said plurality of storage registers includes: (a) means for receiving and maintaining a probability figure associated with each received digit of the codeword that the digit is the digit indicated; and, (b) means for calculating new probabilities to be associated with each digit and for updating said stored probabilities as a function of modifications made to said stored digits to reflect the new true probabilities.
References Cited (Backward Citations)
US3538497A
Cited
US3542756A
Cited
US3665396A
Cited
US3648236A
Cited
US3781791A
Cited
US3818442A
Cited
US4099160A
Cited
USPTO Annuity & Maintenance Windows
| Annuity Stage | Window Opens | Payment Deadline | Surcharge Period Until | Estimated Fee | Status |
|---|---|---|---|---|---|
| 3.5 Years (Year 4) | 1984-10-12 | 1985-04-13 | 1985-10-13 | $2000.00 | Window Closed / Lapsed |
| 7.5 Years (Year 8) | 1988-10-12 | 1989-04-13 | 1989-10-13 | $3760.00 | Window Closed / Lapsed |
| 11.5 Years (Year 12) | 1992-10-12 | 1993-04-13 | 1993-10-13 | $7700.00 | Window Closed / Lapsed |