FORWARD ERROR CORRECTING SYSTEM

• US 3,657,700 A
• Filed: 07/13/1970
• Issued: 04/18/1972
• Est. Priority Date: 07/13/1970
• Status: Expired due to Term

• Current Assignee: Lawrence Lutzker
• Original Assignee: Lawrence Lutzker
• Inventors: Lutzker, Lawrence
• Primary Examiner(s): Atkinson, Charles E.
• Application Number:
  US05/054,505
• Time in Patent Office: 645 Days
• Field of Search: 340/146.1,172.5
• US Class Current: 714/774
• CPC Class Codes: H03M 13/03 Error detection or forward error correction by redundancy in data representation, i.e. code words containing more digits than the source words
• CPC Class Codes: H03M 13/35 Unequal or adaptive error protection, e.g. by providing a different level of protection according to significance of source information or by adapting the coding according to the change of transmission channel characteristics
• CPC Class Codes: H04L 1/0057 Block codes H04L1/0061, H04L1/0064 take precedence

Abstract

An adaptively coded forward error correcting data communications system having the capability of varying error correction potential without the necessity of variation in codes and without the necessity of increasing the percentage redundancy of transmitted data by adaptively varying the block length of the data transmitted utilizing varying data block lengths and in which more than a single block of data may be processed in overlapping time relationship without full duplication of circuitry while permitting decoding and evaluation of the transmitted and received message.

Claims

1. In an adaptively coded forward error correcting digital data communications system having an encoder for adaptively encoding a block of a.k data bits for transmission as a.n data bits in accordance with a selected error correcting code, wherein '"'"''"'"''"'"''"'"'a'"'"''"'"''"'"''"'"' is an integer >

OR = 1 and wherein '"'"''"'"''"'"''"'"'n'"'"''"'"''"'"''"'"' is a block of data bits comprising '"'"''"'"''"'"''"'"'k'"'"''"'"''"'"''"'"' information data bits and '"'"''"'"''"'"''"'"'r'"'"''"'"''"'"''"'"' redundant check data bits;

the improvement comprising in combination a plurality of buffer means for storing blocks of a.k data bits to be encoded, at least one of said buffer means adapted to store a.k data bits for all values of '"'"''"'"''"'"''"'"'a'"'"''"'"''"'"''"'"' up to and including '"'"''"'"''"'"''"'"'am, '"'"''"'"''"'"''"'"' the maximum value of '"'"''"'"''"'"''"'"'a,'"'"''"'"''"'"''"'"' additional buffer means for storing blocks of control bits, feedback register means responsive to each block of a.k data bits read into said feedback register means to generate as a function thereof a block or a.r data bits in accordance with said selected error correcting code and responsive to each block of a.n data bits read into said feedback register means to detect the presence or absence of errors occurring therein, error indicating means coupled to said feedback register means for providing outputs indicative of the detected presence or absence of errors and of the type of any detected errors, control means for selectively reading a first block of a.k data bits into a selected one of said plurality of buffer means, for subsequently reading out said first block of a.k data bits from said selected one of said buffer means into said feedback register means and to an output for transmission, for thereafter reading out said first block of a.r data bits from said feedback register means to said output for transmission, and for selectively reading another block of a.k data bits into another selected one of said plurality of buffer means while said one block of a.n data bits is being read out to said output for transmission, said control means being responsive to said block of control bits received after transmission of said a.n data bits for reading said block of control bits into said additional buffer means and into said feedback register means, and error correcting Means, said control means being responsive to the outputs of said error indicating means for selectively reading the control bits from said additional buffer means and the bits in said feedback register means therefrom into said error correcting means to correct errors in said block of control bits, said control means being additionally responsive to said corrected control bits for selectively and alternatively enabling retransmission of said first block of a.n data bits or encoding of said other block of a.k data bits, and selection of '"'"''"'"''"'"''"'"'ai'"'"''"'"''"'"''"'"' the selected value of '"'"''"'"''"'"''"'"'a'"'"''"'"''"'"''"'"' for encoding each of said blocks of a.k data bits.

2. In a system as claimed in claim 1 wherein said feedback register means includes a plurality of stages equal in number to the value of '"'"''"'"''"'"''"'"'r,'"'"''"'"''"'"''"'"' wherein each of said '"'"''"'"''"'"''"'"'r'"'"''"'"''"'"''"'"' stages includes a plurality of substages equal in number to '"'"''"'"''"'"''"'"'am,'"'"''"'"''"'"''"'"' and including a MOD-2 adder means interconnecting said plurality of stages in accordance with said selected error correcting code.

3. In a system in accordance with claim 2 wherein said control means generates '"'"''"'"''"'"''"'"'am'"'"''"'"''"'"''"'"' minus '"'"''"'"''"'"''"'"'ai'"'"''"'"''"'"''"'"' timing pulses, said control means being responsive to each '"'"''"'"''"'"''"'"'ai'"'"''"'"''"'"''"'"' bits read into said encoder register means for applying said timing pulses to said encoder register means to advance the bits in each of said '"'"''"'"''"'"''"'"'r'"'"''"'"''"'"''"'"' stages through '"'"''"'"''"'"''"'"'am'"'"''"'"''"'"''"'"' minus '"'"''"'"''"'"''"'"'ai'"'"''"'"''"'"''"'"' substages before subsequent bits are read into said encoder register means.

4. In a system as claimed in claim 1 wherein said other buffer means is adapted to store a.k bits for all values of '"'"''"'"''"'"''"'"'a'"'"''"'"''"'"''"'"' up to aj.k bits, wherein '"'"''"'"''"'"''"'"'aj'"'"''"'"''"'"''"'"'<

'"'"''"'"''"'"''"'"'ai'"'"''"'"''"'"''"'"' <

or = '"'"''"'"''"'"''"'"'am,'"'"''"'"''"'"''"'"' and wherein said control means is responsive to the first aj.k data bits of a block of ai.k data bits having been read into said other buffer means for transferring said aj.k bits from said other buffer means to said one encoder buffer means and for reading the remaining '"'"''"'"''"'"''"'"'ai'"'"''"'"''"'"''"'"'-'"'"''"'"''"'"''"'"'aj'"'"''"'"''"'"''"'"' data bits in said block of ai.k data bits into said one buffer means.

5. In an adaptively coded forward error correcting digital data communications system having an encoder for adaptively encoding a block of a.k data bits for transmission as a.n data bits in accordance with a selected error correcting code, wherein '"'"''"'"''"'"''"'"'a'"'"''"'"''"'"''"'"' is an integer >

or = 1 and wherein '"'"''"'"''"'"''"'"'n'"'"''"'"''"'"''"'"' is a block of data bits comprising '"'"''"'"''"'"''"'"'k'"'"''"'"''"'"''"'"' information data bits and '"'"''"'"''"'"''"'"'r'"'"''"'"''"'"''"'"' redundant check data bits and including a decoder for adaptively decoding in accordance with said selected error corrected code, said block of a.n data bits received after transmission;

the improvement comprising in combination a plurality of buffer means for storing blocks of a.k data bits to be decoded, feedback register means responsive to each block of a.n data bits read into said feedback register means to detect the presence or absence of errors occurring therein and responsive to each block of a.k data bits read into said feedback register means to generate as a function thereof a block of a.r data bits in accordance with said selected error correcting code, error indicating means coupled to said feedback register means for providing outputs indicative of the detected presence or absence of errors and of the type of any detected errors, control means responsive to said received block of a.n data bits for reading a.k data bits therefrom into a selected one of said plurality of buffer means and for reading said block of received a.n data bits into said feedback register means, error correcting means, said control means being responsive to the outputs of said error indicating means for selectively reading said a.k data bits from said selecTed buffer means and selected bits from said feedback register means into said error correcting means to correct errors in said a.k data bits, and control bit means for selectively generating blocks of control bits, said control means being additional responsive to said error indicating means for reading out a selected block of control bits from said control bit generating means into said feedback register means to an output for transmission, and for thereafter reading out a block of redundant control bits from said feedback register means to said output for transmission.

6. In a system as claimed in claim 1, including means for adaptively decoding a block of a.n data bits after transmission in accordance with said selected error correcting code to extract said a.k data bits therefrom and to correct any errors occurring therein, wherein said control means is responsive to a first block of a.n data bits received at an input for reading a first block of a.k data bits forming a part thereof into a selected one of said buffer means and for reading said a.n data bits into said feedback register means, wherein said control means is further responsive to the output of said error indicating means after said received a.n data bits have been read into said feedback register means to selectively read out said a.k data bits from said one buffer means and selected bits from said feedback register means through said selective error correction means, to correct errors in said a.k data bits.

7. An adaptive forward error correcting data transmission system for encoding and decoding adaptively variable length blocks of digital data bits in accordance with a selected error correcting code comprising a plurality of buffer storage means for serially receiving a plurality of information data bits, a feedback shift register for generating redundant check data bits as a function of said information data bits in accordance with said code, said register having a number of stages corresponding to the minimum number of redundant check data bits to be generated, said stages including a plurality of substages corresponding to the maximum number of redundant check data bits to be generated, each of said stages including an equal number of substages, means for serially feeding information data bits of selected adaptively variable block length to selected ones of said buffer storage means, means for encoding the information data bits stored in one of said buffer storage means while other information data bits are being fed into an alternate one of said buffer storage means, said encoding means including means for feeding the output of said one buffer storage means into said feedback shift register and simultaneously to a modem for transmission, and means for subsequently feeding the generated redundant data bits from said feedback shift register to said modem, and means for adaptively changing the block length of said digital data bits including means for feeding a selected portion of said block of information data bits into said feedback shift register, and means for shifting said feedback shift register a selected number of times during the interval between each portion of said information data bits until the first bit of each portion is in the last substage in the corresponding stage of said shift register.

8. A system as claimed in claim 7 including means for decoding variable length blocks of digital data bits in accordance with said selected error correcting code including means for simultaneously reading a block of information data bits from said modem into one of said buffer storage means and into said feedback shift register, means responsive to the data bits in said feedback shift register for generating outputs indicative of whether said received data bits contain no errors, contain correctable errors or contain uncorrectable errors, control means responsive to said no error outputs for reading the data bits out of said buffer storage means without change, responsive to said correctable error outputs for selectively combining the data bits read out of said buffer storage means and with data bits read out of said feedback register to correct the correctable errors, and selectively responsive to said outputs, for generating variable length blocks of control bits acknowledging satisfactory transmission of the data bits, selectively requesting adaptive change of the block length of said data bits for subsequent transmission, and requesting retransmission of said variable length block of digital data bits.