초록 ▼

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. Lowe

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.

대표청구항 ▼

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 corr

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).