119)
`United States Patent
`4,271,520
`(11)
`Coombes et al.
`
`[45] Jun. 2, 1981
`
`[54] SYNCHRONIZING TECHNIQUE FOR AN
`ERROR CORRECTING DIGITAL
`TRANSMISSION SYSTEM
`
`[75]
`
`Inventors: Daniel J. Coombes, Winfield, Ill;
`John H, Sangster, Short Hills, N.J.
`
`[73] Assignee: Motorola, Inc., Schaumburg,III.
`
`[21] Appl. No.: 51,938
`
`[22] Filed:
`
`Jun, 25, 1979
`
`Hint, C03 cesssssccsseessnee GO6F 11/10; HO4L 7/02
`[51]
`[52] U.S. Ch. sccssssscccsssesssessnsoneseessnensnee 371/42; 371/5;
`371/47; 375/114
`[58] Field of Search ............. 371/5, 42, 47; 375/106,
`375/108, 114
`
`[56]
`
`3,466,601
`3,550,082
`3,571,794
`3,733,585
`3,824,548
`
`References Cited
`U.S. PATENT DOCUMENTS
`9/1969
`Tong asa iinniaAnion 371/42
`12/1970
`vere 371/42
`Tong .....
`3/1971
`Tong ......
`5/1973 Merlo.....
`
`7/1974
`Sullivan etal. ....
`FOREIGN PATENT DOCUMENTS
`
`wee ST1/42
`
`OTHER PUBLICATIONS
`
`Peterson and Weldon, Error-Codes, Second Edition,
`MIT Press, 1972, pp. 374-376.
`
`Primary Examiner—Charles E. Atkinson
`Attorney, Agent, or Firm—James A. Scheer; James W.
`Gillman
`
`ABSTRACT
`[57]
`Theinstant invention resides in a system, including an
`encoder and a decoder, for the transmission and re-
`trieval of digital data over a transmission medium. The
`encoderincludes an error correction encoding scheme
`which processes the data and produces an encoded bit
`stream including data andparity bits in either an inter-
`spersed or blocked relationship. A transmission bit
`stream is generated by modulo-2 adding the encodedbit
`stream with a predetermined sync sequence, which sync
`sequenceis selected to provide optimum syncdetection
`at the decodersite.
`
`The encoder modulo-2 subtracts said sync sequence
`from the received transmission stream, thereby produc-
`ing a resultant which is monitored by an error correc-
`tion detector. The detector produces an in- or out-of-
`synchronization indication as determined by the num-
`ber of resultant bit stream detected errors.
`
`2741760 3/1979 Fed. Rep. of Germany............. 371/42
`
`8 Claims, 2 Drawing Figures
`
`FROM
`TRANSMISSION
`MEDIUM %
`
`/
`x
`é
`Dn t+kes+92 0;
`22
`
`RECOVERED
`DATA
`
`
`
`
`
`
`
` CODE
`DECODER/
`
`ERROR
`DETECTOR
`
`Apple 1018
`
`Apple 1018
`
`

`

`U.S.Patent
`
`Jun. 2, 1981
`
`4,271,520
`
` ‘
`
`/
`i
`—-ON4KeeeO2 D4
`
`22
`
`FROM
`TRANSMISSION
`MEDIUM *%
`
`
`
`
`
`
`BLOCK
`CODE
`DECODER/
`ERROR
`DETECTOR
`
`

`

`1
`
`4,271,520
`
`SYNCHRONIZING TECHNIQUE FOR AN ERROR
`CORRECTINGDIGITAL TRANSMISSION
`SYSTEM
`
`BACKGROUNDOF THE INVENTION
`
`This invention relates to the digital communication
`art and, more particularly, to a means of, and method
`for resolving synchronization in an. error correction
`encoded transmission.
`Digitally encoded communication systems are well
`known in the data transmission art. In such systems, a
`data bit stream containing digitally encoded informa-
`tion is to be transmitted over a noisy transmission me-
`dium. If the raw information data were transmitted
`without being processed, there would exist a substantial
`probability that portions of the message would be lost
`due to interference from the noisy medium. Therefore,
`this data is normally processed to produce a transmis-
`sion bit stream which, after decoding at the receiver
`site, provides a means to correct or minimize transmis-
`sion medium induced errors. Two examples of error
`correction processing schemes are block and convolu-
`tional type codes.
`Proper decoding of the transmission bit stream re-
`quires that the decoder be able to recognize and syn-
`chronize with a received bit stream signal. One method
`known to the prior art for assuring proper decoding
`synchronizationis the use of a predetermined set of sync
`bits which are sent immediately prior to the information
`data bits. The sync bits follow a predetermined pattern,
`such as one ofthe well known Barker sequences, which
`optimizes the ability of the decoder to recognize and
`synchronize with the transmission bit stream.
`A problem with the aforementioned prior art syn-
`chronization schemes is that the transmission bit stream
`has a minimum length equal to the number of informa-
`tion plus sync bits. In some systems, the numberof sync
`bits must be substantial with respect to the number of
`data bits to insure the desired probability of synchroni-
`zation wherebythe overall message length is quite long,
`thus requiring a lengthy transmission time. It is, of
`course, desirable to reduce transmission time to an abso-
`lute minimum.
`In one approach which minimizes transmission bit
`length, the error correction encoded data is modulo-2
`added with a polynomial generated from a binary word
`generator. The polynomial
`is selected based on the
`nature of the correctable error encoding scheme being
`employed. In so doing, processing circuitry at the de-
`coder may determine from the recovered data bit error
`pattern the condition ofeither a loss of synchronization
`or channel induced ‘errors. However, a fundamental
`problem with this system is that the polynomial
`is
`strictly a function of the particular coding scheme being
`used and, thus, must be suitably updated each time a
`different code is employed. In addition, this scheme
`necessarily employs a tradeoff between the ability to
`detect synchronization and the ability to distinguish
`synchronization from medium induced errors. Thus, the
`system does not provide optimized means for determin-
`ing the state of synchronization.
`In an alternate approach,a parity bit is added at the
`end of each transmitted word. A parity monitor at the
`decoding site detects the condition of disparity. An
`occasional departure from a parity constraint
`is al-
`lowed, howevera grouping which repeatedly produces
`a condition of disparity is used to indicate an error in
`
`10
`
`30
`
`40
`
`45
`
`55
`
`60
`
`65
`
`2
`synchronization. A fundamental problem with this ap-
`proach is that, for many applications, the system does
`notindicate the out-of-sychronization condition quickly
`enough, nor with high enough probability to renderits
`performance acceptable.
`
`SUMMARYOF THE INVENTION
`
`It is an object ofthis invention, therefore, to provide
`an improved digital communication system which mini-
`mizes the number of required transmission bits while
`optimizing the ability of the decoder to determine the
`state of synchronization.
`Briefly, according to the invention, an encoder, for
`use in a digital communication system, is comprised of
`an error correction encoder which processes a data bit
`stream and produces an error correctable encoded bit
`stream corresponding thereto. An encoder storage
`stores a predetermined sequence of sync bits, which
`syncbit sequenceis selected to optimize, at the decoder
`site, detection of sync condition. An encoder combiner,
`preferably of the modulo-2 type, combines the encoded
`bit stream with the sync bit sequence thereby producing
`a transmission bit stream. A decoder processes a trans-
`mission bit stream and comprises a decoder storage
`which has the predetermined sync bit sequence stored
`therein. A decoder combiner, also preferably of the
`modulo-2 type, combines the transmission bit stream
`with a sync bit sequence thereby regenerating, for the
`condition of the decoder being in synchronization with
`the transmission bit stream, the error correctable en-
`codedbit stream. An error correction detector monitors
`the output of the decoder combiner and producesa first
`output, indicative of the decoder being in synchroniza-
`tion with the transmission bit stream, in response to the
`number of detected errors being less than a predeter-
`mined value and produces a second output,indicative of
`the decoderbeing out of synchronization with the trans-
`mission bit stream,
`in response to the number ofde-
`tected errors being greater than or equal to the prede-
`termined value.
`Preferably, the data bit stream is comprised ofa total
`of N bits, whereas the error correction encoder pro-
`duces an encoded bit stream comprised of a total of
`N-+K bits, where K equals the number of generated
`parity bits. The sync bit sequenceis comprised ofa total
`of N+-K bits whereby,for the preferred embodimentof
`bit by bit modulo-2 addition of encoded bits with sync
`bits, the transmission bit stream is comprised ofa total
`of N-+-K bits. This overall length is less than that in the
`prior art which would prefix such N+K bits with a
`given numberofsyncbits.
`BRIEF DESCRIPTION OF THE DRAWINGS
`
`FIG. 1 is a block diagram illustrating a preferred
`embodiment of an encoder according to the invention;
`and
`FIG. 2 is a block diagram illustrating the preferred
`embodiment of a decoder according to the invention.
`DETAILED DESCRIPTION OF THE
`PREFERRED EMBODIMENT OF THE
`INVENTION
`
`Referring to FIG. 1, a series of N data bits, IjI2... Ly,
`are shown being supplied from a data source 10. Data
`source 10 may be comprised of any conventional source
`of data bits, such as a user keyboard, computer output
`and so forth.
`
`

`

`4,271,520
`
`0
`
`15
`
`30
`
`3
`4
`The N data bits are passed to a conventional block
`The outputof storage 30 is constantly monitored by a
`code encoder 12. Block code encoder 12 is of conven-
`block code decoder/error detector 32. Block code
`tional design andis, preferably, of the type discussed in
`decoder/error detector 32 is of conventional design,
`Shu Lin, “An Introduction to Error Correcting
`and is capable of determining the numberoferrors in an
`Codes”, Prentice Hall, 1970, pp 70-75. In operation,
`information plus parity encoded bit stream.In this, the
`block code encoder 12 processes the N data bits and
`preferred embodimentof the invention, the block code
`produces an output error correctable encoded bit
`decoder/error detector 32 is more thoroughly discussed
`stream which,in this the preferred embodiment of the
`in the above identified Shu Lin textbook, at page 80.
`invention, is comprised of the N data bits followed by K
`Since the sync sequence utilized at the encoder and
`parity bits. As is well knownin this art, the parity bits
`subsequently at the decoderis of the type which opti-
`provides a meansto correct for errors occurring during
`mizes the ability to detect synchronization conditions,
`transmission of the data.
`the block code decoder/error detector 32 will detect a
`The encoded bit stream appearing at the output of
`large numberoferrors forall conditions except that in
`block code encoder 12 is applied to one input 14a of a
`which the stored register 30 contains the encoded bit
`conventional modulo-2 adder 14.
`stream appearingat the outputof block code encoder 12
`Applied to the remaining input 145 of modulo-2
`of FIG. 1. Provided within block code decoder/error
`adder14 is the output from a syncbit register 16. Sync
`detector 32 is a threshold level such that for the condi-
`register 16 is comprised of N+-K stages. Stored within
`tion of the numberof detected errors being less than a
`encoder sync storage 16 is a predetermined sync se-
`thresholdlevel, an error detector output 34 is activated
`quencechosen to optimize the ability of the decodersite
`which,
`in turn, closes the contacts of switch 36 to
`to detect synchronization condition. For example, the
`thereby route the error corrected recovered data bit
`sync storage register 16 might store any one of the
`stream I;... Iyto the recovered data output 38. Forall
`Barker sequences for suitable values of N+-K. Upon
`other conditions wherein the number oferrors detected
`activation by a conventional clock 18, the encoded bit
`by error detector 32 is equal to, or greater than this
`stream and sequence, as stored in sync register 16, are
`presetlimit, the output 34 is not activated and switch 36
`modulo-2 added by modulo-2 adder 14 onabit by bit
`is open.
`basis, thereby providing a transmission bit stream
`In summary, the instant invention provides a means
`to minimize the required length of a transmission bit
`stream by eliminating the addition of individual sync
`bits at the beginning of the stream while, on the other
`hand, providing a means to optimize the ability of the
`decoder to sense the sync condition by combining a
`predetermined sync sequence with the encoded bit
`stream.
`While preferred embodiments of the invention have
`been describedin detail, it should be apparent that many
`modifications and variations thereto are possible, all of
`whichfall within the true spirit and scope of the inven- .
`tion.
`Weclaim:
`1. In a digital communication system for the transmis-
`sion and reception of a data bit stream, the improvement
`comprising:
`an encoder for processing said data bit stream, said
`encoder comprising:
`error correction encoder means for receiving said
`data bit stream and producing an error correctable
`encodedbit stream corresponding thereto;
`_
`encoder storage means having a predetermined se-
`quence ofsync bits stored therein, said sync bit
`sequencebeing selected to optimize, at the decoder
`site, detection of an out of sync condition; and
`encoder combining means for predeterminedly com-
`bining said encoded bit stream with said sync bit
`sequence to thereby produce a transmission bit
`stream; and
`a decoderfor processing said transmission bit stream
`comprising:
`decoder storage means having said predetermined
`sync bit sequence stored therein;
`decoder combining means for predeterminedly com-
`bining said transmission bit stream with said sync
`bit sequence thereby regenerating, for the condi-
`tion of the decoder being in synchronization with
`said transmission bit stream, said error correctable
`encodedbit stream;
`
`The transmission bit stream is then passed over a
`transmission medium,such as radio wavesor telephone
`lines, whereby it is received and processed in the pre-
`ferred decoder, shownin FIG. 2. Here, the transmission
`bit stream, which may or may notbe identical to the
`transmission bit stream sent by the encoder of FIG.1,as
`indicated by primes, is received at a decoder input 20.
`The recovered transmission bit stream is fed both to a
`clock recovery circuit 22 and an N+K length shift
`register 24, Clock recoverycircuit 22 is of conventional
`design and recovers the clock signal, such as is pro-
`duced by clock 18 of FIG. 1, from the received trans-
`mission bit stream. This recovered clock signal is then
`passed to the N+K bit shift register 24 causing said
`register to load the received transmission bit stream at
`the proper clockrate.
`Also provided at the decoder is a decoder sync bit
`tegister 26. The decoder sync bit register parallels the
`encodersyncbit register 16 (FIG.1) in that it contains
`N+K stages having the aforementioned predetermined
`sync sequencestored therein.
`Each output, C)... Cv. from the N+K bit shift
`register 24 is applied to a corresponding one of the
`N+K modulo-2 adders, indicated generally at 28. Fed
`to the remaining input of each of the modulo-2 adders
`28 is a corresponding oneofthe syncbits stored in sync
`bit register 26. It should be understood that modulo-2
`addition is the same as modulo-2 subtraction, so that the
`output from the modulo-2 adders 28 is equal
`to the
`modulo-2 difference between a received transmission
`bit stream and the stored sync sequence. These results
`are stored in a N+-K length register 30. Thus, it should
`be obviousthat, for the condition wherein the decoder
`is in synchronization with the transmission bit stream,
`the contents of the storage 30 will be precisely the en-
`coded bit stream producedat the output of the block
`code encoder 12 of FIG. 1.
`
`D,D;... Dy+x, where D) =1,@5),
`D2=h@®S2..-Dwv4K=PKOSN+K.
`
`40
`
`45
`
`50
`
`55
`
`65
`
`

`

`4,271,520
`
`5
`
`10
`
`15
`
`20
`
`5
`6
`data storage means, coupled to the decoder combin-
`(d) providing said predetermined sync bit sequence;
`ing means, for storing the regenerated error cor-
`(e) predeterminedly combining said transmission bit
`rectable encoded bit stream;
`stream with said sync bit sequence suchthat for the
`error correction detector means, coupled to the data
`condition of the decoding operation being in syn-
`chronization with said transmission bit stream said
`storage means, for monitoring the contents of the
`data storage means, thereby monitoring the output
`encoded bit stream is regenerated;
`of said decoder combining means, and producing a
`(f) error correction detecting the resultant of step (e)
`first output, indicative of the decoder being in syn-
`to determine the number of errors occurring
`chronization with said transmission bit stream,
`in
`therein; and
`response to the number of detected errors being
`(g) indicating an in-synchronization condition corre-
`less than a predetermined value and producing a
`sponding to the numberoferrors detected in step
`second output, indicative of the decoder being out
`(f) being less than a predetermined maximum num-
`ber.
`of synchronization with said transmission. bit
`stream, in response to the numberofdetected er-
`6. The method of claim 5 wherein step (c) comprises
`rors being greater than or equal to said predeter-
`the step of:
`mined value.
`modulo-2 adding said encoded bit stream to said sync
`2. The improvementofclaim 1, wherein said encoder
`bit sequence in a bit by bit order;
`combining means and said decoder combining means
`and wherein step.(e) comprises the step of:
`are comprised of modulo-2 adder means.
`modulo-2 substracting said sync bit sequence from
`said transmission bit stream.
`3. The improvementof claim 1 wherein the data bit
`7. The method of claim 5 wherein said data bit stream
`stream is comprised ofa total of N bits; said error cor-
`rection encoder produces an encoded bit stream com-
`is comprised of a total of N bits and wherein:
`prised ofa total of N+K bits; said sync bit sequence is
`step (a) comprises the step of encodingsaid N bit data
`comprised ofa total of N+Kbits and said transmission
`bit stream and producing an encoded bit stream
`25
`bit stream is comprised ofa total of N+-K bits, where N
`comprised ofa total of N+K bits;
`and K are predetermined integers.
`steps (b) and (d) comprise providing a total of N+K
`4. The improvementof claim 2 wherein the data bit
`sync bits; and
`stream is comprised ofa total of N bits; said error cor-
`step (c) comprises the step of combining said N+K
`rection encoder produces an encoded bit stream com-
`bit encoded bit stream with said N+K bit sync
`prised of a total of N+-K bits; said sync bit sequence is
`stream to produce a transmission bit stream having
`comprised of a total of N+K bits and said transmission
`a total of N+K bits, where N and K are predeter-
`bit stream is comprised of a total of N+K bits, where N
`mined integers.
`8. The method of claim 6 wherein said data bit stream
`and K are predetermined integers.
`5. A method for resolving the state of synchroniza-
`is comprised of a total of N bits and wherein:
`tion in an error correction, digital transmission system
`step (a) comprises the step of encodingsaid N bit data
`comprising the steps of encoding a data bit stream by:
`bit stream and producing an encoded bit stream
`(a) error correction encoding said data bit stream
`comprised of a total of N+K bits;
`thereby producing an encoded bit stream;
`steps (b) and (d) comprise the step of providinga total
`(b) providing a predetermined syncbit sequence, said
`of N+K syncbits; and
`sync bit sequencebeing selected to optimize detec-
`step (c) comprises the step of combining said N+K
`tion of an out of sync condition at a decodersite;
`bit encoded bit stream with said N+K bit sync
`(c) predeterminedly combining said encoded bit
`stream to producea transmission bit stream having
`stream with said sync bit sequence thereby produc-
`a total of N+-K bits, where N and K are predeter-
`ing a transmission bit stream;
`mined integers. *
`*
`*
`*
`&
`and decoding said transmission bit stream by:
`
`30
`
`35
`
`40
`
`45
`
`50
`
`55
`
`65
`
`