ENCODER/DECODER FOR CODE WORDS OF VARIABLE LENGTH

• US 3,805,232 A
• Filed: 01/24/1972
• Issued: 04/16/1974
• Est. Priority Date: 01/24/1972
• Status: Expired due to Term

• Current Assignee: Larry Van Allen
• Original Assignee: Larry Van Allen
• Inventors: Allen, Larry Van
• Primary Examiner(s): Morrison, Malcolm A.
• Assistant Examiner(s): Malzahn, David H.
• Application Number:
  US05/219,998
• Time in Patent Office: 813 Days
• Field of Search: 340/146.1,146.1AL,146.1AV
• US Class Current: 714/779
• CPC Class Codes: H03M 13/17 Burst error correction, e.g. error trapping, Fire codes

Abstract

An encoder/decoder is described in which a conventional feedback shift register for encoding cyclic code words is augmented by an auxiliary feedback shift register. The auxiliary register is interconnected in such a manner that it provides appropriate feedback paths for enabling error correction for a code word of any shortened length.

Claims

1. An encoder/decoder for encoding binary words having a variable number k'"'"''"'"' of information bits into cyclic code words of variable length n'"'"''"'"', including a checking portion of a predetermined number n-k of check bits, for transmission over a transmission channel, in which the cyclic code words are generated by a cyclic code generating polynomial P(x) capable of generating, in accordance with a preselected cyclic code, cyclic code words of a maximum normal length n, of which a maximum k bits are information bits and the remainder n-k are check bits, where k'"'"''"'"' <

or = k and n '"'"''"'"' <

or = n, for decoding encoded cyclic code words of length n'"'"''"'"' received over said transmission channel into corresponding binary words of length k'"'"''"'"', and for providing error correcting patterns for said decoded binary words, said encoder/decoder comprising;

A. a first set of n-k shift register stages for use both in encoding and decoding operations and interconnected by circuit means so as to assume successive states, in accordance with the preselected cyclic code, and ultimately representing the checking portion in the case of an encoded word and representing an error correcting pattern in the case of a decoded binary word;

B. first gating means included withiN said circuit means and connected between the output of the last register stage and the inputs of predetermined other register stages of said first set of shift register stages, said first gating means being enabled to provide feedback to said predetermined register stages during the encoding of the k'"'"''"'"' information bits of said binary word into the n-k check bits of said code words and being disabled thereafter;

C. second gating means connected between the output of the last register stage and said transmission channel, said second gating means being enabled after k'"'"''"'"' inputs to said first set of shift register stages, to pass the contents of said n-k register stages, representing the checking portion of the encoded code word, to said transmission channel;

D. a second set of n-k shift register stages for use in decoding operations only, said register stages being arranged to shift in response to each bit of a code word received over said transmission channel and being interconnected to provide feedback to predetermined ones of said second set of shift register stages, said second set of shift register stages being further arranged to shift in parallel with said first set of shift register stages during a decoding operation;

E. means for clearing said second set of shift register stages and setting a logical 1 into the highest order register stage upon the initiation of a decoding operation prior to the receipt of a code word to be decoded;

F. a set of n-k gating means each being selectively gated by the contents of one of said second set of shift register stages and connecting a particular bit of the code word received over said transmission channel to selected ones of said first set of shift register stages, said second set of shift register stages thereby dividing the received code word by x modulo P(x);

G. a zero detector, responsive to the contents of a predetermined number of low order register stages of said first set of shift register stages, for indicating the presence or absence of a zero residue condition in said register stages after n'"'"''"'"' bits of the code word have been received and decoded;

H. means responsive to an indication of the absence of a zero residue condition for enabling said first gating means and for supplying a succession of logical 0'"'"''"'"'s to said first set of shift register stages from said transmission channel until said zero detector indicates a zero residue condition; and

I. means responsive to an indication of the presence of a zero residue condition for disabling said first gating means and enabling said second gating means, to pass the contents of said n-k register stages, representing an error pattern associated with the decoded binary word, to said transmission channel for utilization by exterior error-correcting means.

2. The endoder/decoder of claim 1, in which said second set of shift register stages is interconnected in accordance with the factored form P1(x) (xc - 1) of the code generating polynomial P(x).

3. A decoder for decoding cyclic code words of variable length n'"'"''"'"' received over an input portion of a transmission channel into binary words having a variable number k'"'"''"'"' of information bits, said cyclic code words being of the type generated by a cyclic code generating polynomial P(x) capable of generating, in accordance with a preselected cyclic code, cyclic code words of a maximum normal length n, of which a maximum k bits are information bits and the remainder n-k are check bits, where k '"'"''"'"' <

or = k and n'"'"''"'"' <

or = n, said cyclic code words of variable length n'"'"''"'"' to be decoded each containing a checking portion of a predetermined number n-k of check bits, and for providing error correcting patterns for said decoded binary words, said decoder comprising;

A. a firsT set of n-k shift register stages interconnected by circuit means so as to assume successive states, in accordance with the preselected cyclic code, and ultimately representing the error correcting pattern for a decoded binary word;

B. first gating means included within said circuit means and connected between the output of the last register stage and the inputs of predetermined other register stages of said first set of shift register stages;

C. second gating means connected between the output of the last register stage of said first set of shift register stages and an output portion of said transmission channel;

D. a second set of n-k shift register stages, said register stages being arranged to shift in response to each bit of a code word received over said input portion of said transmission channel and being interconnected to provide feedback to predetermined ones of said second set of shift register stages, said second set of shift register stages being further arranged to shift in parallel with said first set of shift register stages during a decoding operation;

E. means for clearing said second set of shift register stages and setting a logical 1 into the highest order register stage upon the initiation of a decoding operation prior to the receipt of a code word to be decoded;

F. a set of n-k gating means each being selectively gated by the contents of one of said second set of shift register stages and connecting a particular bit of the code word received over the input portion of said transmission channel to said first set of shift register stages, said second set of shift register stages thereby dividing the received code word by x modulo P(x);

G. a zero detector, responsive to the contents of a predetermined number of low order register stages of said first set of shift register stages, for indicating the presence or absence of a zero residue condition in said register stages after n'"'"''"'"' bits of the code word have been received and decoded;

H. means responsive to an indication of the absence of a zero residue condition for enabling said first gating means and for supplying a succession of logical 0'"'"''"'"'s to said first set of shift register stages from the input portion of said transmission channel until said zero detector indicates a zero residue condition; and

I. means responsive to an indication of the presence of a zero residue condition for disabling said first gating means and enabling said second gating means, to pass the contents of said n-k register stages, representing an error pattern associated with the decoded binary word, to the output portion of said transmission channel for utilization by exterior error-correcting means.

4. The decoder of claim 3, in which said second set of shift register stages is interconnected in accordance with the factored form P1(x) (xc - 1) of the code generating polynomial P(x).