US3622985A
Expired / Lapsed
US
⏱️ 0.0 years remaining
Optimum error-correcting code device for parallel-serial transmissions in shortened cyclic codes
Assignee: International Business Machines Corp
•
Filing: 1969-11-25
•
Granted: 1971-11-23
•
Expires: 1989-11-25
Abstract
Abstract Errors in transmitted shortened cyclic code words are detected and corrected by unusually simple apparatus at a receiver and transmitter connected together by a bus. A 72-bit parallel code word, actually comprising a 64-bit data portion and an eight bit checking portion, is conceptually expanded and treated as if it were 108 bits long. At both the transmitter and receiver, the word is split into four sequential groups and sent to an eightposition parallel feedback shift register via an 18-bit bus and intermediate circuits. Each bit on the bus is assigned a channel and the register positions are connected to selected channels through summing circuits, and to each other through feedback circuits, of varying complexity. At the transmitter, the final contents of the register are the checking portion of the code word. At the receiver, if there is an error, the final contents of the shift register indicate which bit in the data portion of the code word must be corrected. The eighteen bits on the bus are connected to selected ones of 27 conceptual channels of which 18 are real (connected to the bus) and nine are phantoms (not connected to anything). While no summing circuit connections are required for the phantom channels, each one of the 27 conceptual channels nevertheless has associated with it a known number of circuit connections. The amount of hardware is greatly reduced by connecting to the bus those conceptual channels requiring the least number of circuit connections and designating as phantoms those conceptual channels which would have required the most summing circuit connections. The total complexity of the feedback circuits and associated error location and correction circuits are similarly lessened.
Inventors
- 👤 John K Ayling
- 👤 Hua-Tung Lee
Bibliographic Details
Application Number
—
Jurisdiction
US
Data Source
google_patents
Last Synchronized
2026-10-26 21:25
CPC Classifications
H; H03; H03M; H03M13/00; H03M13/03; H03M13/05; H03M13/13; H03M13/19
Claims Analysis
Total Claims: 11
Claim 1
Independent Claim
254 words
Apparatus to be used in generating at a transmitter checking portions for, and detecting and correcting at a receiver errors in, n-bit code words each comprising a k-bit data portion and an n- k bit checking portion in accordance with a preselected cyclic code, the code words being manifested in n/c sequential groups of c bits each on c-signal lines; there being provided: a register comprising n- k positions, each having an input and an output, for assuming successive states, in accordance with the preseleCted cyclic code, ultimately representative of the checking portion in the case of the transmitter and of the existence and location of a number of errors in the code word data portion in the case of the receiver; n- k-summing means each having an output, connected to a different register position input, and inputs for accepting c bits of the code word from selected ones of c+ pi conceptual channels represented by said c-signal lines and pi phantom lines each channel being associated with selected summing means in accordance with the preselected cyclic code; n- k feedback means each having an output, connected to a different register position input, and inputs for accepting selected register position outputs in accordance with the preselected cyclic code; and interconnection means, connecting the real channels (selected ones of the c-lines) with the summing means inputs and the register position outputs with the feedback means inputs, in accordance with the preselected cyclic code, defining as phantoms selected ones of those channels requiring the most connections.
Claim 2
Dependent Claim
254 words
Apparatus to be used in generating at a transmitter checking portions for, and detecting and correcting at a receiver errors in, n-bit code words each comprising a k-bit data portion and an n- k bit checking portion in accordance with a preselected cyclic code, the code words being manifested in n/c sequential groups of c bits each on c-signal lines; there being provided: a register comprising n- k positions, each having an input and an output, for assuming successive states, in accordance with the preseleCted cyclic code, ultimately representative of the checking portion in the case of the transmitter and of the existence and location of a number of errors in the code word data portion in the case of the receiver; n- k-summing means each having an output, connected to a different register position input, and inputs for accepting c bits of the code word from selected ones of c+ pi conceptual channels represented by said c-signal lines and pi phantom lines each channel being associated with selected summing means in accordance with the preselected cyclic code; n- k feedback means each having an output, connected to a different register position input, and inputs for accepting selected register position outputs in accordance with the preselected cyclic code; and interconnection means, connecting the real channels (selected ones of the c-lines) with the summing means inputs and the register position outputs with the feedback means inputs, in accordance with the preselected cyclic code, defining as phantoms selected ones of those channels requiring the most connections.
Claim 3
Dependent Claim
242 words
In combination: a number of sources of parallel input data signals representative of information bits and check bits; a first predetermined number of storage positions, each having an input and an output, sequentially responsive to information bits to ultimately indicate corresponding check bits in accordance with a preselected cyclic code and responsive to information and check bits to ultimately indicate the presence and location of errors in the information bits; entry means connecting a second predetermined number of input data sources in selected groups with individual storage position inputs in accordance with a first connection pattern determined by the preselected cyclic code, said second predetermined number being greater than said first number; and feedback means connecting the outputs of the storage positions in predetermined groups with individual inputs in accordance with a second connection pattern determined by the preselected cyclic code, all connection patterns possible for the preselected cyclic code being representable by a matrix having one column for each storage position and one row for each state in the sequence of states possible for the preselected cyclic code, the first connection pattern being established by a third predetermined number of consecutive rows of said matrix beginning with the first row said third number exceeding said second predetermined number, and the second connection pattern being established by a second contiguous number of rows, following the said third number of rows in the sequence equal, and corresponding, to the number of storage positions.
Claim 4
Dependent Claim
242 words
In combination: a number of sources of parallel input data signals representative of information bits and check bits; a first predetermined number of storage positions, each having an input and an output, sequentially responsive to information bits to ultimately indicate corresponding check bits in accordance with a preselected cyclic code and responsive to information and check bits to ultimately indicate the presence and location of errors in the information bits; entry means connecting a second predetermined number of input data sources in selected groups with individual storage position inputs in accordance with a first connection pattern determined by the preselected cyclic code, said second predetermined number being greater than said first number; and feedback means connecting the outputs of the storage positions in predetermined groups with individual inputs in accordance with a second connection pattern determined by the preselected cyclic code, all connection patterns possible for the preselected cyclic code being representable by a matrix having one column for each storage position and one row for each state in the sequence of states possible for the preselected cyclic code, the first connection pattern being established by a third predetermined number of consecutive rows of said matrix beginning with the first row said third number exceeding said second predetermined number, and the second connection pattern being established by a second contiguous number of rows, following the said third number of rows in the sequence equal, and corresponding, to the number of storage positions.
Claim 5
Independent Claim
189 words
The method of establishing parallel-input parallel-feedback connections for an n- k stage shift register to generate n- k-checking bits or error pattern syndrome bits useful to detect and correct errors in n-bit code words, in accordance with a shortened (n, k)-cyclic code having associated therewith an autonomous state matrix having n- k columns and N rows (where N is the cycle length of the extended code); comprising the steps of: dividing the n information bits into n/c sequential portions each having c real bits, corresponding to information bits, interleaved with additional pi phantom bits; associating selected groups of the sequential c+ pi portions with summing inputs of respective ones of the n- k shift register stages in accordance with successive rows of said matrix; associating selected groups of the n- k outputs of the shift register with other summing inputs of the individual register stages in accordance with other successive rows of said matrix; and connecting the associated groups to said inputs in accordance with said matrix rows assuming the convention that phantom information bits have constant-zero value and positioNal correspondence with matrix rows which require the most connections.
Claim 6
Independent Claim
189 words
The method of establishing parallel-input parallel-feedback connections for an n- k stage shift register to generate n- k-checking bits or error pattern syndrome bits useful to detect and correct errors in n-bit code words, in accordance with a shortened (n, k)-cyclic code having associated therewith an autonomous state matrix having n- k columns and N rows (where N is the cycle length of the extended code); comprising the steps of: dividing the n information bits into n/c sequential portions each having c real bits, corresponding to information bits, interleaved with additional pi phantom bits; associating selected groups of the sequential c+ pi portions with summing inputs of respective ones of the n- k shift register stages in accordance with successive rows of said matrix; associating selected groups of the n- k outputs of the shift register with other summing inputs of the individual register stages in accordance with other successive rows of said matrix; and connecting the associated groups to said inputs in accordance with said matrix rows assuming the convention that phantom information bits have constant-zero value and positioNal correspondence with matrix rows which require the most connections.
Claim 7
Dependent Claim
175 words
In apparatus including an n- k-stage register for indicating existence and position of error in n-bit groups of signals carried in parallel on c lines, said signals intended to represent n-bit code words of a shortened (n,k)-cyclic error correcting code (n- k less than c) the improvement comprising: n- k-summing networks having individual outputs connecting with inputs of respective stages of said indicating register, and having individual first and second groups of inputs; means for connecting said first groups of inputs of said summing networks in parallel to respective predetermined groups of feedback outputs of said register; means for connecting said second groups of inputs of said summing networks in parallel to respective predetermined groups of said c-lines; said predetermined groups of said register feedback outputs and said lines being designated in association with a submatrix of c+ n- k selected rows of the autonomous generating matrix of said (n,k) code, the submatrix being formed by selecting from among the rows of said matrix only rows containing fewer than a predetermined number of nonzero-digit elements.
Claim 8
Dependent Claim
175 words
In apparatus including an n- k-stage register for indicating existence and position of error in n-bit groups of signals carried in parallel on c lines, said signals intended to represent n-bit code words of a shortened (n,k)-cyclic error correcting code (n- k less than c) the improvement comprising: n- k-summing networks having individual outputs connecting with inputs of respective stages of said indicating register, and having individual first and second groups of inputs; means for connecting said first groups of inputs of said summing networks in parallel to respective predetermined groups of feedback outputs of said register; means for connecting said second groups of inputs of said summing networks in parallel to respective predetermined groups of said c-lines; said predetermined groups of said register feedback outputs and said lines being designated in association with a submatrix of c+ n- k selected rows of the autonomous generating matrix of said (n,k) code, the submatrix being formed by selecting from among the rows of said matrix only rows containing fewer than a predetermined number of nonzero-digit elements.
Claim 9
Dependent Claim
37 words
Apparatus according to claim 4 in which the said selection of submatrix rows is designed to effect economies in the numbers of parallel inputs handled by said summing networks and thereby effect economies in said summing networks.
Claim 10
Dependent Claim
73 words
Apparatus according to claim 5 wherein said selection of rows of said matrix establishes a unique shift in the relative positions of said lines and in the associated error position indications manifested by said register when error occurs on one of said lines, whereby in effect plural phantom lines may be considered as positioned between certain of the said c-lines; said phantom lines being viewable as carrying phantom signals of constant 0 value.
Claim 11
Dependent Claim
45 words
The apparatus of claim 6 wherein particular error syndrome states occurring in said register at particular parallel shift times, are associated with the space and time positions of error in particular signals on particular lines of the aggregate set of said c-lines and phantom lines.
References Cited (Backward Citations)
US3465287A
Cited
US3452328A
Cited
USPTO Annuity & Maintenance Windows
| Annuity Stage | Window Opens | Payment Deadline | Surcharge Period Until | Estimated Fee | Status |
|---|---|---|---|---|---|
| 3.5 Years (Year 4) | 1974-11-22 | 1975-05-24 | 1975-11-23 | $2000.00 | Window Closed / Lapsed |
| 7.5 Years (Year 8) | 1978-11-22 | 1979-05-24 | 1979-11-23 | $3760.00 | Window Closed / Lapsed |
| 11.5 Years (Year 12) | 1982-11-22 | 1983-05-24 | 1983-11-23 | $7700.00 | Window Closed / Lapsed |