Error correcting code device for parallel-serial transmissions

Claim 2

In apparatus including an n-k stage residue accumulating register for checking and correcting errors in groups of n signals by arrangement of the signals in an (n,k) cyclic code system the improvement comprising: means for forming n-k parallel signals representing predetermined logic functions of n-k distinct subcombinations of groups of c+n-k parallel signals, each group consisting of c of said n signals and the n-k outputs of said register, where c is a number greater than n-k and less than n; and means for applying said n-k signals representing logic functions in parallel, as residue representing inputs pertaining to said code, to inputs of respective stages of said residue accumulating register.

Claim 3

In apparatus including an n-k stage feedback shift register and means associated therewith for detecting and correcting errors in groups of n signals arranged in an (n,k) shortened cyclic code the improvement comprising: logical decoding means activated coincidentally with detection of a nonzero check residue state in said register which indicates occurrence of a said error in a said group of n signals for analyzing said residue and conditionally responsive thereto to provide immediate specific indication of error location in a particular subgroup of c of said n signals, when the said residue state corresponds to a row in one particular subgroup of c rows of an n-row by n-k column autonomous matrix listing associated with said code, where c is greater than n-k and less than n.

Claim 4

In apparatus including an n-k stage feedback shift register and means associated therewith for detecting and correcting errors in groups of n signals arranged in an (n,k) shortened cyclic code the improvement comprising: logical decoding means activated coincidentally with detection of a nonzero check residue state in said register which indicates occurrence of a said error in a said group of n signals for analyzing said residue and conditionally responsive thereto to provide immediate specific indication of error location in a particular subgroup of c of said n signals, when the said residue state corresponds to a row in one particular subgroup of c rows of an n-row by n-k column autonomous matrix listing associated with said code, where c is greater than n-k and less than n.

Claim 5

In apparatus including an n-k stage parallel input parallel feedback shift register and means associated therewith for detecting and correcting errors in groups of n signals arranged in an (n,k) shortened cyclic code the improvement comprising: a plurality of c logical decoding means, c being an integer greater than n-k and less than n, activated in parallel upon detection of a said error in said signals to analyze the residue output of said register and recognize occurrence therein of any of c predetermined states uniquely associated with the position of a said error in said signals; said predetermined states corresponding to c respective rows of an n-k column by n row autonomous matrix listing uniquely associated with said code.

Claim 6

In apparatus including an n-k stage parallel input parallel feedback shift register and means associated therewith for detecting and correcting errors in groups of n signals arranged in an (n,k) shortened cyclic code the improvement comprising: a plurality of c logical decoding means, c being an integer greater than n-k and less than n, activated in parallel upon detection of a said error in said signals to analyze the residue output of said register and recognize occurrence therein of any of c predetermined states uniquely associated with the position of a said error in said signals; said predetermined states corresponding to c respective rows of an n-k column by n row autonomous matrix listing uniquely associated with said code.

Claim 7

In apparatus for handling bidirectional transmission of intelligence signals in parallel sets of c signals at a time, a device useful for encoding raw data groups of k of said signals c at a time into respective groups of n signals arranged according to an (n,k) cyclic code (n>c>n-k) and for decoding encoded groups of n of said signals, when received c at a time in said (n,k) code form, in order to detect and correct errors in the received coded signals, comprising: buffer means for storing n binary signals; a source of first groups of n binary signals, each group consisting of k raw data signals and n-k terminal zero signals, manifested in successive sets of c parallel signals; means for transferring said k raw data signals and n-k terminal zero signals of each first group from said source to n respective stages of said buffer means in the real time of occurrence of said sets of c parallel signal manifestations; means operated in time coordination with said n signal transferral to said buffer to derive n-k check signals from said sets of c parallel signal manifestations, said check signals bearing a cyclic code relationship to said k raw data signals, and to deposit said check signals in said n-k stages of said buffer means receiving said terminal zero signals for further handling with said raw data signals as supplemental error checking/error correcting signals; a source of a supply of second groups of n signals arranged in an (n,k) cyclic error checking/error correcting code form in which each group of n signals consists of k raw data signals and n-k supplemental signals having error checking/error correcting code significance; means coupled to said second group source for transferring said second groups of n signals to respective stages of said buffer; means for operating said check signal deriving means relative to parallel sets of c signals in said buffer to form a final check residue signal with n-k elements for each said second group of n signals transferred to said buffer from said second source; means coupled to said buffer for subjecting at least the k raw data signal portions of said second groups in said buffer to further handling in parallel signal sets of c signals at a time; and means operated upon occurrence of error indication in said final check residue and coordinated in real time with said further handling of said parallel signal groups of c signals for operating said check signal deriving means to subject said final check residue to parallel feedback shift manipulations designed individually to produce unique indications of specific locations of error within respective said sets of c further handled signals in timed coordination with the said further handling.

Claim 8

In apparatus for handling bidirectional transmission of intelligence signals in parallel sets of c signals at a time, a device useful for encoding raw data groups of k of said signals c at a time into respective groups of n signals arranged according to an (n,k) cyclic code (n>c>n-k) and for decoding encoded groups of n of said signals, when received c at a time in said (n,k) code form, in order to detect and correct errors in the received coded signals, comprising: buffer means for storing n binary signals; a source of first groups of n binary signals, each group consisting of k raw data signals and n-k terminal zero signals, manifested in successive sets of c parallel signals; means for transferring said k raw data signals and n-k terminal zero signals of each first group from said source to n respective stages of said buffer means in the real time of occurrence of said sets of c parallel signal manifestations; means operated in time coordination with said n signal transferral to said buffer to derive n-k check signals from said sets of c parallel signal manifestations, said check signals bearing a cyclic code relationship to said k raw data signals, and to deposit said check signals in said n-k stages of said buffer means receiving said terminal zero signals for further handling with said raw data signals as supplemental error checking/error correcting signals; a source of a supply of second groups of n signals arranged in an (n,k) cyclic error checking/error correcting code form in which each group of n signals consists of k raw data signals and n-k supplemental signals having error checking/error correcting code significance; means coupled to said second group source for transferring said second groups of n signals to respective stages of said buffer; means for operating said check signal deriving means relative to parallel sets of c signals in said buffer to form a final check residue signal with n-k elements for each said second group of n signals transferred to said buffer from said second source; means coupled to said buffer for subjecting at least the k raw data signal portions of said second groups in said buffer to further handling in parallel signal sets of c signals at a time; and means operated upon occurrence of error indication in said final check residue and coordinated in real time with said further handling of said parallel signal groups of c signals for operating said check signal deriving means to subject said final check residue to parallel feedback shift manipulations designed individually to produce unique indications of specific locations of error within respective said sets of c further handled signals in timed coordination with the said further handling.

Claim 9

In apparatus for detecting plural errors and correcting single errors in code word groups of n intelligence signals arranged in an (n,k) single error correcting/double error detecting cyclic code form, said apparatus including n-k stage parallel input-parallel feedback shift register means for developing n-k signal check residue indications by manipulation of said n signal groups to indicate the error status of a code word group of n of said intelligence signals and to develop by further logical manipulation of said check residue indications correction indications useful to designate for correction locations of specific single errors within a said code word group of n signals containing an error, the improvement comprising: parity check means operated to check the parity of said check residue indication and to condition said further logical Manipulation for error correction upon the recognition of odd parity in said check residue indication.

Claim 10

In apparatus for detecting plural errors and correcting single errors in code word groups of n intelligence signals arranged in an (n,k) single error correcting/double error detecting cyclic code form, said apparatus including n-k stage parallel input-parallel feedback shift register means for developing n-k signal check residue indications by manipulation of said n signal groups to indicate the error status of a code word group of n of said intelligence signals and to develop by further logical manipulation of said check residue indications correction indications useful to designate for correction locations of specific single errors within a said code word group of n signals containing an error, the improvement comprising: parity check means operated to check the parity of said check residue indication and to condition said further logical Manipulation for error correction upon the recognition of odd parity in said check residue indication.

Claim 11

In apparatus for handling signals in a parallel-serial form upon a given number c of parallel signal conveying channels a device useful alternately for encoding signals into (n,k) cyclic code form (n>c>n-k) whereby errors in said signals may be detected and corrected in other apparatus, and for decoding encoded signals from said (n,k) form in order to carry out said detection and correction of errors locally, said device comprising: an n-k stage register having n-k parallel inputs and n-k parallel outputs; n-k modulo two adder circuits each having: multiple connections to outputs of a respective subset of said c channels for receiving parallel direct signal inputs, multiple connections to a respective subset of outputs of said register for receiving parallel feedback signal inputs and an output connected to one respective input of said register for parallel conditioning thereof to feedback shift residue states; first means for detecting a first predetermined combinational state in said register as indication of nonoccurrence of errors in a group of n signals manifested c at a time in said c signal channels; second means for detecting c different predetermined combinational states in said register, all different from the said first state, as indicators of error locations in respective predetermined sets of said c signals manifested in said channels; and means for operating combinations of said foregoing means sequentially to provide alternatively: (a) n-k check digit indications to supplement a group of k raw data signals and n-k terminal zero signals received through said c channels and to form therewith a code word group of n signals in an (n,k) cyclic code or (b) error check and error correction indications specific to n signals representing an (n,k) code word group manifested c at a time in said c channels.

Claim 12

In apparatus for handling signals in a parallel-serial form upon a given number c of parallel signal conveying channels a device useful alternately for encoding signals into (n,k) cyclic code form (n>c>n-k) whereby errors in said signals may be detected and corrected in other apparatus, and for decoding encoded signals from said (n,k) form in order to carry out said detection and correction of errors locally, said device comprising: an n-k stage register having n-k parallel inputs and n-k parallel outputs; n-k modulo two adder circuits each having: multiple connections to outputs of a respective subset of said c channels for receiving parallel direct signal inputs, multiple connections to a respective subset of outputs of said register for receiving parallel feedback signal inputs and an output connected to one respective input of said register for parallel conditioning thereof to feedback shift residue states; first means for detecting a first predetermined combinational state in said register as indication of nonoccurrence of errors in a group of n signals manifested c at a time in said c signal channels; second means for detecting c different predetermined combinational states in said register, all different from the said first state, as indicators of error locations in respective predetermined sets of said c signals manifested in said channels; and means for operating combinations of said foregoing means sequentially to provide alternatively: (a) n-k check digit indications to supplement a group of k raw data signals and n-k terminal zero signals received through said c channels and to form therewith a code word group of n signals in an (n,k) cyclic code or (b) error check and error correction indications specific to n signals representing an (n,k) code word group manifested c at a time in said c channels.

Claim 13

The apparatus of claim 6, wherein said (n,k) code is a shortened cyclic code and said c predetermined states of said register which are recognized by said second detecting means correspond to the c last rows of an n row by n-k column autonomously produced matrix derived by design simulation of the serial polynomial division of a predetermined 1,0,0,0..... signal train representation by a predetermined generating polynomial associated with the logical organization of said n-k modulo two adder circuits.

Claim 14

The apparatus of claim 6 wherein said operating means controls development of said supplemental check digit indications stated at (a) by first repeatedly operating said modulo two adder circuits to transfer sums of signals obtained in parallel from said c channels and register output stages into said register while k raw data signals and n-k terminal zero signals are being manifested in said c channels in parallel signal groups of c signals, and thereafter making the residue output of said register available for further handling as supplemental check digit representations which together with said k received signals form a representation of a said (n,k) cyclic code word.

Claim 15

The apparatus of claim 6 wherein said (n,k) code is capable of providing double error detection and single error correction.

Claim 16

The apparatus of claim 6 wherein said operating means is adapted to control development of said error check and error correction indications by: first repeatedly operating said modulo two adder circuits to transfer into said register stages sums of said signals obtained in parallel from said respective subsets of said c CHANNELS and said n-k register outputs, until a total of n signals representing an (n,k) code word have been manifested in said c channels; immediately thereafter operating said first and second detecting means relative to said register to recognize either occurrence of said first predetermined state in said register as indication of nonoccurrence of error in said n signals manifested in said c channels, or conditioned upon absence of recognition of said first state, to recognize occurrence of any one of said c other predetermined states as indication of a respective specific location of error within the first-manifested group of c of said n signals manifested in said c channels; thereafter, conditioned upon recognition of nonoccurrence of any of said c predetermined states and nonoccurrence of said first predetermined state, operating said modulo two adder circuits with said c channels disconnected to transfer sums of only said register feedback subcombinations into said register stages and repeating the operation of the second detecting means to recognize occurrence of any of said c predetermined states in said register as indicators of specific error locations in the second-manifested group of c signals previously manifested in said c channels; and thereafter conditioned upon absence of recognition of any of said c states repeating the operations of parallel feedback residue shifting and recognition testing, as described in the preceding paragraph, until either error is located in one of a group of c of said n received signals or a total of (n/c)-1 iterations of said operation have been performed; in the latter event said operating means being adapted to provide indication that error in uncorrectable form is present in the said n manifested signals.

Claim 17

The apparatus of claim 10 including means to develop an indication of the parity of a state representation in said register, wherein said operating means is adapted to provide the control necessary for the operations of claim 11 subject to the additional condition that said parity means provide an odd parity indication coincident with the operation of said first state detecting means before any further operations are performed to develop said error location indications.

Claim 18

Device useful alternately to develop n-k check signals to supplement k raw data signals, and thereby form a code word in a double error detecting/single error correcting (n,k) cyclic code system, while said k signals are handled relative to said device in parallel signal groups of c data signals (n>c>n-k), and to develop error check and error locating indications for correcting errors on the fly in n signals representing a code word in said (n,k) cyclic code system while a raw data portion of said n signals is being handled relative to the device in sequential parallel signal groups of c signals, said device comprising: a plurality of sets of c lines carrying recurring signals in parallel; a word buffer register having capacity to store at least n binary signals; a check residue register having n-k binary stages; n-k modulo two adders having outputs coupled to inputs of respective stages of said check residue register for transferring n-k modulo two sum function signals in parallel signal sets either to encode said signals by appendage thereto of supplemental signals developed in said residue register or to check said signals for error and conditionally correct errors therein by examination of check and location designating indications developed in said residue register; first means for connecting n-k different plural signal subcombinations of feedback signals obtained from Outputs of stages of said register to inputs of respective said adders; second means for connecting n-k different subcombinations of c lines from a selected one of said sets of lines to inputs of respective said adders; third means for connecting one of said sets of lines selectively to receive outputs of one of the c-element sections of said word buffer register; fourth means for connecting the n-k outputs of said residue register to n-k respective predetermined stages of said word buffer register; fifth and sixth means for respectively effecting other input and output signal connections relative to said word buffer register; first means for controlling said first, second and fourth connecting means conjointly while k raw data signals are carried over one of said sets of lines to develop thereby supplemental check digit signals related to said data signals while assembling a representation of said data signals in said word buffer register and for storing said check signals together with said representation in said word buffer register as a said (n,k) cyclic code word unit; first detection means coupled to said residue register for detecting therein a first predetermined residue state condition useful to distinguish nonoccurrence of error in a checked word signal encoded in said (n,k) code; second detection means coupled to said residue register for detecting the parity condition (odd or even) of the residue state condition instantly stored in said residue register; third detection means, coupled to said residue register and activated conditionally when said first and second detection means provide coincident indications of absence of said first predetermined residue state condition and presence of a condition of odd parity in said residue register, for providing c distinct recognition indications of c predetermined different residue conditions when respective said conditions are present in said register while said third detection means is coincidentally in said activated condition; a c-line output bus; seventh connecting means for transferring a said assembled word representation out of said word register to said output bus in sequential parallel signal groups of c signals at a time; first means conditioned to be operated coordinately with said seventh connecting means by error and odd parity indications obtained jointly from said first and second detection means for utilizing indications provided by said third detection means for correcting specific signal elements in said c signal groups of said word representation on the fly during said transfer to said output bus; second means conditioned to be operated coordinately with said seventh connecting means by error and odd parity indications obtained jointly from said first and second detection means, and by further indication of noncompletion of error correction obtained from said coordinately operated correcting means, for operating only said first connecting means relative to said residue register to effect modification by feedback only of the instant residue state condition thereof intermediate successive transfers of said c signal groups; and third means conditioned to be operated upon completion of the transfer of a said word representation out of said register by error and odd parity indications obtained jointly from said first and second detection means, and by further indication of noncompletion of error correction obtained from said coordinately operated correcting means, for producing indication denoting presence of noncorrectable error in said transferred word.

Claim 19

Device useful alternately to develop n-k check signals to supplement k raw data signals, and thereby form a code word in a double error detecting/single error correcting (n,k) cyclic code system, while said k signals are handled relative to said device in parallel signal groups of c data signals (n>c>n-k), and to develop error check and error locating indications for correcting errors on the fly in n signals representing a code word in said (n,k) cyclic code system while a raw data portion of said n signals is being handled relative to the device in sequential parallel signal groups of c signals, said device comprising: a plurality of sets of c lines carrying recurring signals in parallel; a word buffer register having capacity to store at least n binary signals; a check residue register having n-k binary stages; n-k modulo two adders having outputs coupled to inputs of respective stages of said check residue register for transferring n-k modulo two sum function signals in parallel signal sets either to encode said signals by appendage thereto of supplemental signals developed in said residue register or to check said signals for error and conditionally correct errors therein by examination of check and location designating indications developed in said residue register; first means for connecting n-k different plural signal subcombinations of feedback signals obtained from Outputs of stages of said register to inputs of respective said adders; second means for connecting n-k different subcombinations of c lines from a selected one of said sets of lines to inputs of respective said adders; third means for connecting one of said sets of lines selectively to receive outputs of one of the c-element sections of said word buffer register; fourth means for connecting the n-k outputs of said residue register to n-k respective predetermined stages of said word buffer register; fifth and sixth means for respectively effecting other input and output signal connections relative to said word buffer register; first means for controlling said first, second and fourth connecting means conjointly while k raw data signals are carried over one of said sets of lines to develop thereby supplemental check digit signals related to said data signals while assembling a representation of said data signals in said word buffer register and for storing said check signals together with said representation in said word buffer register as a said (n,k) cyclic code word unit; first detection means coupled to said residue register for detecting therein a first predetermined residue state condition useful to distinguish nonoccurrence of error in a checked word signal encoded in said (n,k) code; second detection means coupled to said residue register for detecting the parity condition (odd or even) of the residue state condition instantly stored in said residue register; third detection means, coupled to said residue register and activated conditionally when said first and second detection means provide coincident indications of absence of said first predetermined residue state condition and presence of a condition of odd parity in said residue register, for providing c distinct recognition indications of c predetermined different residue conditions when respective said conditions are present in said register while said third detection means is coincidentally in said activated condition; a c-line output bus; seventh connecting means for transferring a said assembled word representation out of said word register to said output bus in sequential parallel signal groups of c signals at a time; first means conditioned to be operated coordinately with said seventh connecting means by error and odd parity indications obtained jointly from said first and second detection means for utilizing indications provided by said third detection means for correcting specific signal elements in said c signal groups of said word representation on the fly during said transfer to said output bus; second means conditioned to be operated coordinately with said seventh connecting means by error and odd parity indications obtained jointly from said first and second detection means, and by further indication of noncompletion of error correction obtained from said coordinately operated correcting means, for operating only said first connecting means relative to said residue register to effect modification by feedback only of the instant residue state condition thereof intermediate successive transfers of said c signal groups; and third means conditioned to be operated upon completion of the transfer of a said word representation out of said register by error and odd parity indications obtained jointly from said first and second detection means, and by further indication of noncompletion of error correction obtained from said coordinately operated correcting means, for producing indication denoting presence of noncorrectable error in said transferred word.

Claim 20

Device according to claim 12 wherein n, k and c are respectively equal to 72, 64, and 18, and said code word representations are assembled in said word buffer register in four parallel transfer operations through said second conneCting means and removed from said word buffer register through said connecting means in four parallel transfer operations coordinated with operations of said coordinately operated means.