US3623155A
Expired / Lapsed
US
⏱️ 0.0 years remaining
Optimum apparatus and method for check bit generation and error detection, location and correction
Assignee: International Business Machines Corp
•
Filing: 1969-12-24
•
Granted: 1971-11-23
•
Expires: 1989-12-24
Abstract
Abstract Errors in code words transmitted over a communication path are detected and corrected by optimum apparatus at transmitting and receiving ends of the path. Illustratively, a 72 bit parallel code word, comprising a 64 bit information portion and an eight bit check portion is communicated between a transmitter and a receiver. A check bit generator at the transmitter generates eight check bits as a function of the 64 information bits, each check bit being associated with a number of information bits (a check bit and its associated information bits forming a ''''code group''''). The information bits and check bits are communicated to the receiver where an error detector compares check bits generated from the received information bits with the received check bits and an error locator analyzes any mismatch to determine the location of an error. An error corrector then corrects any information or check bit which is identified as incorrect by the error locator. The check bit generator at the transmitter supplies signals, at outputs corresponding to the check bits, by Exclusive ORing the information bits in its code group, in accordance with a single error correction and double error detection (SEC/DED) code. The error detector examines each code group separately by Exclusive ORing both its information and check bits in accordance with the same code and supplies syndrome signals manifesting the result of the examination. Error detection and correction are possible because, upon transmission, each code group contains an even number of bits (even parity), only one of which is a check bit, and each bit of each code word is a member of an odd number of code groups. At the receiver, a single correctable error is assumed to have occurred if an odd number of received code groups contains an odd number of bits (odd parity) and an uncorrectable double error is assumed to have occurred if an even number of code groups have odd parity. Single errors are then located and corrected as an AND function of the odd parity code groups. The check bit generator, error detector and error locator are designed in accordance with a technique for using a minimum number of components and a uniform number of components in each parallel signal path. Among the design goals are: each unique code group should substantially contain the same number of bits, each information bit must be a member of an odd number of code groups greater than one, and each check bit must be a member of a different code group. The number of code groups to which each information bit is assigned is determined by first exhausting the lowest odd number of code group combinations available before going to the next odd number of combinations.
Inventors
- 👤 Mu-Yue Hsiao
- 👤 Eugene Kolankowsky
Bibliographic Details
Application Number
—
Jurisdiction
US
Data Source
google_patents
Last Synchronized
2026-11-03 02:12
CPC Classifications
H; H03; H03M; H03M13/00; H03M13/03; H03M13/05; H03M13/13; H03M13/19
Claims Analysis
Total Claims: 26
Claim 1
Independent Claim
193 words
In a system for detecting and correcting errors in code words having a plurality of information bits and a plurality of check bits each assigned to a number of code groups, an improved check bit generator comprising: input means for accepting signals manifesting information bits; a number of logic groupings, one for each code group, each connected to the input means to accept those information bit signals that are assigned to its code group and to supply at an output one check bit signal manifesting a function of the information bit signals in its code groups; and a plurality of connection means for connecting said input means and said logic groupings, an odd number of said connection means connecting each information bit signal from said input means to an equal odd number of logic groupings, said odd number of connection means and said odd number of logic groupings increasing in order from to less than where r is the number of check bits and m is an odd number greater than one, and said connection means connecting a substantially equal number of information bit signals from said input means to each logic grouping.
Claim 2
Dependent Claim
193 words
In a system for detecting and correcting errors in code words having a plurality of information bits and a plurality of check bits each assigned to a number of code groups, an improved check bit generator comprising: input means for accepting signals manifesting information bits; a number of logic groupings, one for each code group, each connected to the input means to accept those information bit signals that are assigned to its code group and to supply at an output one check bit signal manifesting a function of the information bit signals in its code groups; and a plurality of connection means for connecting said input means and said logic groupings, an odd number of said connection means connecting each information bit signal from said input means to an equal odd number of logic groupings, said odd number of connection means and said odd number of logic groupings increasing in order from to less than where r is the number of check bits and m is an odd number greater than one, and said connection means connecting a substantially equal number of information bit signals from said input means to each logic grouping.
Claim 3
Dependent Claim
25 words
The check bit generator of claim 1, wherein the check bit manifests an Exclusive OR function of the information bit signals in its code group.
Claim 4
Dependent Claim
46 words
The check bit generator of claim 2, wherein the code word is divided into bytes containing substantially equal numbers of bits and wherein said connection means provide each information bit signal to logic groupings in order from to less than groupings for each byte in turn.
Claim 5
Dependent Claim
201 words
In a system for detecting and correcting errors in code words having a plurality of information bits and a plurality of check bits each assigned to a number of code groups, an improved error detector comprising: input means for accepting signals manifesting information bits and check bits; a number of logic groupings, one for each code group, each connected to the input means to accept those information and check bit signals that are assigned to its code group and to supply at an output one syndrome signal manifesting a function of the information and check bit signals in its code group; and a plurality of connection means for connecting said input means and said logic groupings an odd number of said connection means connecting each information and check bit signal from said input means to an equal odd number of logic groupings, said odd number of connection means and said odd number of logic groupings increasing in order from to less than where r is the number of check bits and m is an odd number greater than one, said connection means connecting a substantially equal number of information and check bit signals from said input means to each logic grouping.
Claim 6
Dependent Claim
201 words
In a system for detecting and correcting errors in code words having a plurality of information bits and a plurality of check bits each assigned to a number of code groups, an improved error detector comprising: input means for accepting signals manifesting information bits and check bits; a number of logic groupings, one for each code group, each connected to the input means to accept those information and check bit signals that are assigned to its code group and to supply at an output one syndrome signal manifesting a function of the information and check bit signals in its code group; and a plurality of connection means for connecting said input means and said logic groupings an odd number of said connection means connecting each information and check bit signal from said input means to an equal odd number of logic groupings, said odd number of connection means and said odd number of logic groupings increasing in order from to less than where r is the number of check bits and m is an odd number greater than one, said connection means connecting a substantially equal number of information and check bit signals from said input means to each logic grouping.
Claim 7
Dependent Claim
26 words
The error detector of claim 4, wherein the syndrome signal manifests an Exclusive OR function of the information and check bit signals in its code group.
Claim 8
Dependent Claim
47 words
The error detector of claim 5, wherein the code word is divided into bytes containing substantially equal numbers of bits and wherein said connection means provide each information and check bit signals to logic groupings in order from to less than groupings for each byte in turn.
Claim 9
Dependent Claim
27 words
The error detector of claim 6, wherein n equals one for check bit signals and m equals an odd number greater than one for information bit signals.
Claim 10
Dependent Claim
43 words
The error detector of claim 4, wherein a signal indicating the existence of any errors is generated as an OR function of said syndrome signals and signals distinguishing single from double errors are generated as an Exclusive OR function of said syndrome signal.
Claim 11
Dependent Claim
89 words
The system of claim 4, wherein there is provided an improved error locator comprising: syndrome sensing means, connected to said logic grouping outputs, for supplying said syndrome signals; and a plurality of logic circuits, connected to said syndrome sensing means, for supplying on a plurality of outputs, each associated with a different one of the code word bits, signals indicating the location of an error, each circuit output signal being an AND function of at least those syndrome signals which are a function of the associated code word bit.
Claim 12
Dependent Claim
89 words
The system of claim 4, wherein there is provided an improved error locator comprising: syndrome sensing means, connected to said logic grouping outputs, for supplying said syndrome signals; and a plurality of logic circuits, connected to said syndrome sensing means, for supplying on a plurality of outputs, each associated with a different one of the code word bits, signals indicating the location of an error, each circuit output signal being an AND function of at least those syndrome signals which are a function of the associated code word bit.
Claim 13
Dependent Claim
89 words
The system of claim 5, wherein there is provided an improved error locator comprising: syndrome sensing means, connected to said logic grouping outputs, for supplying said syndrome signals; and a plurality of logic circuits, connected to said syndrome sensing means, for supplying on a plurality of outputs, each associated with a different one of the code word bits, signals indicating the location of an error, each circuit output signal being an AND function of at least those syndrome signals which are a function of the associated code word bit.
Claim 14
Dependent Claim
89 words
The system of claim 6, wherein there is provided an improved error locator comprising: syndrome sensing means, connected to said logic groupings outputs, for supplying said syndrome signals; and a plurality of logic circuits, connected to said syndrome sensing means, for supplying on a plurality of outputs, each associated with a different one of the code word bits, signals indicating the location of an error, each circuit output signal being an AND function of at least those syndrome signals which are a function of the associated code word bit.
Claim 15
Dependent Claim
89 words
The system of claim 7, wherein there is provided an improved error locator comprising: syndrome sensing means, connected to said logic grouping outputs, for supplying said syndrome signals; and a plurality of logic circuits, connected to said syndrome sensing means, for supplying on a plurality of outputs, each associated with a different one of the code word bits, signals indicating the location of an error, each circuit output signal being an AND function of at least those syndrome signals which are a function of the associated code word bit.
Claim 16
Dependent Claim
213 words
In combination: a check bit generator for generating a plurality of check bits as a function of selected ones of a plurality of information bits, the related check and information bits forming a code group; a communication path for transmitting said bits; an error detector, connected to said path, for monitoring the code groups and generating as a function of the monitored bits one syndrome signal for each code group; a logic circuit, connected to said error detector, operative by one or more syndrome signals to indicate the existence of an error, operative by an odd number of syndrome signals of one kind to indicate the existence of a condition treated as a correctable single error and operative by an even number of syndrome signals of said one kind to indicate the existence of a condition treated as an uncorrectable error; an error locator, connected to said error detector, operative as a function of syndrome signals from the error detector, to supply a plurality of indications eaCh corresponding to one of the plurality of information and check bits on the communication path; and an error corrector, connected to said path and to said error locator, operative as a function of the indications from the error locator to correct incorrect bits on said path.
Claim 17
Dependent Claim
213 words
In combination: a check bit generator for generating a plurality of check bits as a function of selected ones of a plurality of information bits, the related check and information bits forming a code group; a communication path for transmitting said bits; an error detector, connected to said path, for monitoring the code groups and generating as a function of the monitored bits one syndrome signal for each code group; a logic circuit, connected to said error detector, operative by one or more syndrome signals to indicate the existence of an error, operative by an odd number of syndrome signals of one kind to indicate the existence of a condition treated as a correctable single error and operative by an even number of syndrome signals of said one kind to indicate the existence of a condition treated as an uncorrectable error; an error locator, connected to said error detector, operative as a function of syndrome signals from the error detector, to supply a plurality of indications eaCh corresponding to one of the plurality of information and check bits on the communication path; and an error corrector, connected to said path and to said error locator, operative as a function of the indications from the error locator to correct incorrect bits on said path.
Claim 18
Dependent Claim
92 words
The combination of claim 14, wherein the check bit generator further comprises: a plurality of circuit means for generating one check bit as a function of all information bits in its code group, each circuit means being associated with a substantially equal number of information bits and each information bit being associated with an odd number of circuit means, said odd number being chosen from the numbers 3, 5,...,r in order, where 5 approaches the number of check bits, all possible combinations of each number being used before the next is chosen.
Claim 19
Dependent Claim
99 words
The combination of claim 14, wherein the error detector further comprises: a plurality of circuit means for generating one syndrome signal as a function of all information and check bits in a code group, each circuit means being associated with a substantially equal number of information and check bits and each information and check bit being associated with an odd number of circuit means, said odd number being chosen from the numbers 1, 3, 5, ...,r in order, where r approaches the number of check bits, all possible combinations of each number being used before the next is chosen.
Claim 20
Dependent Claim
99 words
The combination of claim 14, wherein the error detector further comprises: a plurality of circuit means for generating one syndrome signal as a function of all information and check bits in a code group, each circuit means being associated with a substantially equal number of information and check bits and each information and check bit being associated with an odd number of circuit means, said odd number being chosen from the numbers 1, 3, 5, ...,r in order, where r approaches the number of check bits, all possible combinations of each number being used before the next is chosen.
Claim 21
Dependent Claim
241 words
In a system for correcting at a receiver code words sent by a transmitter, wherein: the transmitter includes a check bit generator for generating a plurality of check bits as a function of a plurality of information bits, associated check and information bits defining a code group; and the receiver includes an error detector for supplying a number of syndrome signals, equal to the number of code groups, as a function of the information and check bits in each code group, and an error locator operative in accordance with the syndrome signals to identify the location in the code words of correctable errors; the improvement comprising: a. a check bit generator comprising sets of Exclusive OR circuits, each set corresponding to one row of the matrix shown in FIG. 2 and having an output labeled by a one in columns C1 through C8 and inputs labeled by ones in columns D0 through D63 for its row; b. an error detector comprising sets of Exclusive OR circuits, each set corresponding to one row of the matrix shown in FIG. 2 and having one output for each row and inputs labeled by ones in all columns for its row; and c. an error locator comprising sets of AND circuits, each set corresponding to one column of the matrix shown in FIG. 2 and having one output for each column and at least those inputs labeled by ones in all rows for its column.
Claim 22
Dependent Claim
241 words
In a system for correcting at a receiver code words sent by a transmitter, wherein: the transmitter includes a check bit generator for generating a plurality of check bits as a function of a plurality of information bits, associated check and information bits defining a code group; and the receiver includes an error detector for supplying a number of syndrome signals, equal to the number of code groups, as a function of the information and check bits in each code group, and an error locator operative in accordance with the syndrome signals to identify the location in the code words of correctable errors; the improvement comprising: a. a check bit generator comprising sets of Exclusive OR circuits, each set corresponding to one row of the matrix shown in FIG. 2 and having an output labeled by a one in columns C1 through C8 and inputs labeled by ones in columns D0 through D63 for its row; b. an error detector comprising sets of Exclusive OR circuits, each set corresponding to one row of the matrix shown in FIG. 2 and having one output for each row and inputs labeled by ones in all columns for its row; and c. an error locator comprising sets of AND circuits, each set corresponding to one column of the matrix shown in FIG. 2 and having one output for each column and at least those inputs labeled by ones in all rows for its column.
Claim 23
Independent Claim
124 words
The method of designing an error detecting and correcting system by representing the connections by a matrix of ones defining the relationship of k information bits and n-k check bits, wherein each column represents an information or check bit and each row a code group containing related information and check bits, including the steps of: assigning each check bit to one different code group; assigning information bits to three code groups until all possible combinations of tHree code groups are exhausted; assigning additional information bits to five code groups until all possible combinations of five code groups are exhausted; and assigning further information bits to m code groups, where m is each odd number taken in order of increasing magnitude until n-k is reached.
Claim 24
Independent Claim
124 words
The method of designing an error detecting and correcting system by representing the connections by a matrix of ones defining the relationship of k information bits and n-k check bits, wherein each column represents an information or check bit and each row a code group containing related information and check bits, including the steps of: assigning each check bit to one different code group; assigning information bits to three code groups until all possible combinations of tHree code groups are exhausted; assigning additional information bits to five code groups until all possible combinations of five code groups are exhausted; and assigning further information bits to m code groups, where m is each odd number taken in order of increasing magnitude until n-k is reached.
Claim 25
Dependent Claim
153 words
In a system for correcting at a receiver errors in code words sent by a transmitter, each code word including information bits and check bits generated as a function of selected associated information bits, each information bit being associated with an odd number of check bits; an improved means for distinguishing single errors from double errors, comprising: a first logic circuit, having a number of inputs each responsive to a function of a different check bit and its associated information bits and having an output for indicating that an error has occurred; and a second logic circuit, having a number of inputs each responsive to aforesaid function of a different check bit and its associated bits and having as another input thereto an output from said first logic circuit indicating that an error occurred, and having a number of outputs for indicating which of a single error and a double error has occurred.
Claim 26
Dependent Claim
153 words
In a system for correcting at a receiver errors in code words sent by a transmitter, each code word including information bits and check bits generated as a function of selected associated information bits, each information bit being associated with an odd number of check bits; an improved means for distinguishing single errors from double errors, comprising: a first logic circuit, having a number of inputs each responsive to a function of a different check bit and its associated information bits and having an output for indicating that an error has occurred; and a second logic circuit, having a number of inputs each responsive to aforesaid function of a different check bit and its associated bits and having as another input thereto an output from said first logic circuit indicating that an error occurred, and having a number of outputs for indicating which of a single error and a double error has occurred.
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) | 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 |