United States Patent (19)
`Gates
`
`(54) FORWARD ERROR CORRECTION SYSTEM
`75) Inventor:
`John Gates, San Jose, Calif.
`TIW Systems, Inc., Sunnyvale, Calif.
`73 Assignee:
`(21) Appl. No.: 77,800
`22 Filed:
`Jul. 27, 1987
`... G06F 11/10
`51 Int. C.4 .....
`52 U.S. C. ...................................................... 371/43
`58 Field of Search ........................ 371/43, 44, 45, 46
`(56)
`References Cited
`U.S. PATENT DOCUMENTS
`3,373,404 3/1968 Webb .................................... 371/37
`... 371/43
`3,697,950 10/1972 Low etal
`4,032,886 6/1977 En et al......
`... 371/45
`371/43
`4,293,951 10/1981 Rhodes ...
`... 371/45
`4,539,684 9/1985 Kloker ...
`4,641,327 2/1987 Wei....................................... 371/43
`OTHER PUBLICATIONS
`Berlekamp, Algebraic Coding Theory, McGraw-Hill,
`1968, pp. 331-338.
`Primary Examiner-Charles E. Atkinson
`Attorney, Agent, of Firm-Flehr, Hohbach, Test,
`Albritton & Herbert
`57
`ABSTRACT
`The system first incorporates an encoder which utilizes
`
`Patent Number:
`11
`(45) Date of Patent:
`
`4,908,827
`Mar. 13, 1990
`
`a rate convolutional encoder to encode the data and a
`supplementary coding system for converting the rate
`coded data to a nominal rate. Thereafter, in order that
`the encoded data fits within the fixed frame length
`which has been adopted as a standard for the present
`TDMA transmission system, a portion of the excess
`data in each frame of encoded data put out by the en
`coder must be deleted or punched out. These bits are
`spaced throughout the frame to minimize the effect of
`the punchout routine.
`On the decoding side of the system, bits must be rein
`serted in the same place where they were deleted in the
`encoder. Because these bits were removed at the en
`coder, the decoder cannot possibly know what they
`were. It is not important to know what they were, but
`rather when in the received bit stream they would have
`occurred. In these places, place holding bits that are
`marked as such are inserted. This function is achieved
`by arbitrarily inserting either 1's or 0's in the bit stream,
`and providing an accompanying bit stream which incor
`porates flag bits for marking the existence of these place
`holding bits. Later processing in the decoder then sim
`ply treats these bits as place holders. That is, they do not
`add information that can help correct errors, nor do
`they cause errors.
`
`19 Claims, 5 Drawing Sheets
`
`Output " " Do to
`
`Output "Q" Do to
`
`input Data
`10
`
`
`
`D/Z
`
`Ck
`
`Punch Out
`
`O Clk
`Control
`
`Out Clk
`
`
`
`
`
`17
`
`IPR2018-01474
`Apple Inc. EX1008 Page 1
`
`

`

`US. Patent
`
`Mar. 13,1990
`
`Sheet 1 of5
`
`4,908,827
`
`
`
`NF_o::o;o=_=waflaammmFan
`
`
`
`Flllllllll..
`
`
`
`oFooveFFFEmco;F
`
`_omomoF”a“o=_=
`
`Emfiw
`
`2.25a.gag
`
`\JV\(\VJ
`
`.
`
`oFoo__ch
`
`
`
`oFoo__UHw_:oumomm<
`rk\}\flf\oFF:_
`
`
`
`quFsow%wwwwwwwww
`
`
`
`oFoo__op
`
`
`
`
`
`m~_ncyan“aafizoF.
`
`___oo_o
`
`.FFFoFc
`
`_MFW_owow_o=o=
`
`mF_moFooF=Q:_hlFooFFoF
`
`mo_«m_~oFm_a:_u
`
`
`
`m=o_¥o004=F30lzozam=
`
`\
`
`
`
`
`
`mFoocozuomchF_smcoLF_u:_u
`
`FFFooFo=_=
`
`FFFFoFo:0:
`
`comoso
`
`
`
`.m.ll.N\FHmLovoocmown
`
`
`
`mm.Ho~\Fum”Femouoo_o=#o<
`
`
`
`owumfi_mDace~=QF=o
`
`numfi_movenFags.
`
`mm
`
`mmmmFm
`
`mm
`
`mm
`
`mmFm
`
`__mNEN
`
`|PR2018—0.1474
`
`Apple Inc. EX1008 Page 2
`
`IPR2018-01474
`Apple Inc. EX1008 Page 2
`
`
`

`

`U.S. Patent
`
`Mar. 13, 1990
`
`Sheet 2 of 5
`
`4,908,827
`
`D? DQ „ „ ! nd? nO
`
`
`
`
`
`
`
`
`
`× 10 |Z/Q
`
`0||
`D? od \ ndu |
`
`IPR2018-01474
`Apple Inc. EX1008 Page 3
`
`

`

`U.S. Patent
`
`Mar. 13, 1990
`
`Sheet 3 of 5
`
`4908,827
`
`ZZ
`
`InOHONnd
`
`WOÀI
`
`
`
`
`
`103TES 8/W
`
`< |
`
`TVNO | LINTOAN00
`
`31W8 Z/I WOH+
`
`IPR2018-01474
`Apple Inc. EX1008 Page 4
`
`

`

`U.S. Patent
`US. Patent
`
`m13,lmM
`
`f
`
`8
`
`53%E.
`
`5a2:.
`
`
`"lib.m=5“5%".Swe<3umiS
`M_;2Et=6_§____-__§s._m
`
`530
`
`:m
`
`,
`
`3555
`
`4908,827
`4,908,827
`
`._<_Ema
`
`_
`
`
`
`><da85.13
`
`
`
`
`
`
`
`
`
`
`
`X.
`
`85.80a025:
`
`5.5839.
`
`as;.
`
`gm.
`
`=<Lm=m
`as a
`?ea e ed
`
`.3528mamm\<.
`
`
`
`Ea,:m.
`
`=02.—
`
`Egzmast
`
`zo“E
`=mm=cn
`us co e /
`
`’—
`H
`
`D—
`al
`
`-::<o-—<
`s as as is a
`
`'m=
`ea are
`
`|PR2018—O1474
`
`Apple Inc. EX1008 Page 5
`
`IPR2018-01474
`Apple Inc. EX1008 Page 5
`
`
`
`
`

`

`U.S. Patent
`
`Mar. 13, 1990
`
`Sheet 5 of 5
`
`4,908,827
`
`||
`
`10HTES
`D –
`
`jº f7 7.7
`
`# | |
`
`
`
`
`
`
`
`
`
`
`
`
`
`IPR2018-01474
`Apple Inc. EX1008 Page 6
`
`

`

`1.
`
`FORWARD ERROR CORRECTION SYSTEM
`
`15
`
`20
`
`CROSS-REFERENCE TO RELATED
`APPLICATIONS
`This invention is especially useful with the TDMA
`Terminal disclosed in the application of Joseph Deal,
`entitled A Multipoint TDMA Terminal, filed Dec. 6,
`1985 under Ser. No. 805,616, and assigned to the As
`10
`signee of this invention.
`BRIEF SUMMARY OF INVENTION
`The present invention is directed generally to the
`field of digital satellite communication systems, and
`more particularly to an error correction scheme for use
`in such a system.
`Communications channels of all types are subject to
`errors due to noise within the channel itself. It is desir
`able to eliminate, or at least reduce, the effects of these
`errors as much as possible.
`There exist two distinct techniques for accomplishing
`this task. One technique requires detecting the presence
`of errors at the receiving end of the communications
`link, then informing the transmitting end that an error
`25
`occurred. The data involved can then be retransmitted
`until it is correctly received. This type of error correc
`tion is known as Automatic-Repeat-Request (ARQ).
`This technique is mentioned herein only for complete
`ness of presentation. The technique of interest to this
`application follows.
`The second technique is to send a certain extra
`amount of information along with the original data,
`This extra information is derived from the original data
`stream itself in some manner known to the receiver as
`well as the transmitter.
`When errors occur, the receiver uses the excess infor
`mation to locate the errors and correct them without
`further communication with the transmitter. This type
`of correction is called Forward-Error-Correction
`(FEC).
`w
`There are two widely used types of forward error
`correction systems in common use in the communica
`tions industry: block codes, and convolutional codes.
`Block codes have the property that the information
`to be coded is broken up into normally equally sized
`45
`units of a convenient size. These blocks have data added
`to them in some manner that is dependent upon the data
`itself, creating a new block of somewhat larger size that
`may or may not resemble the original data. However,
`by understanding the coding scheme utilized, the new
`50
`block of data can be analyzed and the original data
`extracted, even if errors have been created in the data.
`Convolutional codes take a different approach. Con
`volutional codes work, not on blocks of data, but on a
`continuum of data. Data is serially and continuously
`55
`passed into a circuit called an encoder. The encoder is
`of sufficient size to instantaneously look at the current
`data and some amount of previous data. The system
`then outputs a continuous stream of data at a higher
`rate, either more data being transmitted faster, or more
`60
`data over a longer time period.
`Block codes inherently lend themselves to a TDMA
`product such as used in satellite communication because
`of the inherent block structure of a TDMA. They are
`straight forward to implement and yield error perfor
`65
`mance gains that are very predictable.
`Convolutional codes are generally more difficult to
`implement and performance prior to construction can
`
`4,908,827
`2
`only be approximated. In addition, they are by defini
`tion not structured into a block format. They have,
`however, one important characteristic. Convolutional
`decoders can make greater use of the received informa
`tion more easily than block decoders.
`This additional information is in terms of the quality
`of the received bit stream. Block decoders can easily
`only recognize that a received data bit is a one or a zero.
`Convolutional decoders can make use of information
`regarding how closely a particular received bit is to a
`perfect one or a perfect zero.
`W
`In other words, is the incoming data bit not only
`probably a 1 or a 0, but is there a high probability or a
`low probability that it is 1 or 0. This additional capabil
`ity yields a dramatic improvement in the code's error
`correction performance.
`The major drawback to using a convolutional coder
`is that due to the memory of past events required (re
`membering the description of the coder) excess data is
`generated that cannot be passed through the remainder
`of the TDMA system, because of the exactly fixed
`length of each frame of data to be transmitted. This
`excess data must somehow be stripped out.
`Therefore it is an objective of this invention to pro
`vide an error correction system which is especially
`useful with a TDMA communications satellite system.
`Another objective of this invention is to provide a con
`volutional coder capable of operating in a TDMA envi
`ronment. An objective of this invention to provide a
`convolutional coder which includes means for eliminat
`ing the excess data to provide frames of data for trans
`mission of the defined frame length without a significant
`deterioration of the accuracy of the system.
`A convolutional coder can operate in a TDMA envi
`ronment which requires transmission of data frames of
`defined length by just periodically stopping and starting
`the coder at convenient places in the original data
`stream. This technique is referred to as truncation and is
`well documented in the literature of the art. However,
`though truncation does indeed yield a frame structure
`to a convolutional code, the size of the frame required
`turns out to be inconvenient.
`To understand the modifications made in this inven
`tion of prior art approaches, the following definition
`must be understood. The rate of a code is the number of
`bits entered into the encoder divided by the number
`leaving it. Thus if 750 bits enter and 1000 are output the
`code is said to be an R = rate code.
`In a convolutional code of the type described herein,
`a few extra bits must be forced or inserted into the
`encoder at the end of each input block of unencoded
`data in order to insure all information bits are equally
`encoded. This yields a number of output bits that is not
`the number desired by the system. Example: R= I/O.
`R=Real code rate
`I = Number of unencoded information bits
`O= Number of output bits from the encoder
`In a system where the convolutional coding technique
`of the present invention is used, the result of forcing
`extra bits into the encoder at the end of each block is
`that the number of actual output bits from the encoder
`will be (I-T)/R where T = Number of extra bits re
`quired to fully encode the unencoded information bits in
`each block of data.
`As an example assume a coder that is nominally a rate
`it coder with 100 input information bits and five addi
`
`30
`
`35
`
`40
`
`IPR2018-01474
`Apple Inc. EX1008 Page 7
`
`

`

`10
`
`15
`
`4,908,827
`3
`4.
`tional bits required to thoroughly encode the original
`of the encoded bits without significantly degrading the
`data. Then O = (100+5)/ = 210.
`accuracy of the encoded data.
`But the desired number of output bits from the en
`On the decoding side of the system, bits must be
`reinserted in the same place where they were deleted in
`coder to form a frame of data for TDMA transmission
`the encoder. Obviously, because these bits were re
`was only 200. The elimination of these excess 10 bits to
`moved at the encoder, the decoder cannot possibly
`form blocks of convolutional coded data for TDMA
`know what they were. But according to the present
`transmission is the objective of the present invention.
`system, it is not important to know what they were, but
`An objective of this invention to provide an im
`rather when in the received bit stream they would have
`proved type convolutional error correction scheme for
`occurred. In these places, place holding bits that are
`use in systems where an R= I/O relationship must be
`preserved.
`marked as such are inserted. This function is achieved
`by arbitrarily inserting either 1's or 0's in the bit stream,
`A more specific objective of this invention is to per
`and providing an accompanying bit stream which incor
`mit the use of data bit elimination (or puncturing) in
`porates flag bits for marking the existence of these place
`environments wherein the total number of output bits
`holding bits. Later processing in the decoder then sim
`must be some exact number that is related to the original
`ply treats these bits as place holders. That is, they do not
`number of input information bits prior to the insertion
`add information that can help correct errors, nor do
`of the excess bits required for the full encoding of the
`they cause errors.
`original data.
`It is recognized that this technique may degrade the
`Yet another objective of this invention is to provide a
`error correction performance of the system to some
`20
`system which provides for puncturing in combination
`limited extent. But if used in combination with a straight
`with a data rate modification.
`convolutional coding technique, the number of bits lost
`The invention will be useful with any type code con
`is so small as to not significantly affect performance. If
`version. It is disclosed here using several examples,
`used in combination with a rate changing technique to
`including a rate coder.
`be described below, i.e., from the code which results
`25
`It must be noted that puncturing or punchout of data
`from the convolutional coding step to a rate code, the
`bits is occurring for two different purposes in this sys
`number of bits deleted to accomplish the rate conver
`ten disclosure. Punchout of encoded data bits occurs to
`sion is so much greater than the number deleted of the
`carry out a data rate conversion. In this invention, how
`excess bits in the tail portion (on the order of 100 to 1),
`ever, punchout must also occur for a second reason.
`the overall performance of the system is extremely close
`30
`That is, it usually occurs that the data output from the
`to that of a rate system, while being created utilizing
`encoder is not in frames of the length which the system
`standard components.
`is designed to handle. That is, in the preferred embodi
`ment being disclosed herein, the rate conversion does
`BRIEF DESCRIPTION OF DRAWINGS
`not produce a bit stream which is divided into blocks of
`The features and advantages of this invention will be
`35
`exactly the same length as the frame of data to be trans
`more clearly understood from the following figures
`mitted in a typical transmission. To overcome this prob
`wherein,
`lem, the length of the blocks of data put out by the
`FIG. 1A shows the conversion of the incoming bit
`encoder must be modified to fit the defined frame struc
`stream to, I, Q data; FIG. 1B shows a scheme for punch
`ture length.
`ing out data including theoretical approach to analysis
`40
`One cannot simply truncate the end of each block of
`of the errors produced by the punchout scheme of this
`the data stream. If these last few bits were just directly
`invention according to the present invention;
`eliminated, necessary data would be lost because each
`FIGS. 2A and 2B show the essential elements of the
`original bit to be recovered by the decoder is deter
`punchout electronics of the present invention;
`mined by a sequence of bits received at the receiver.
`FIGS. 3 and 4 show in block diagram form the en
`45
`Therefore, it is an object of this invention to develop
`coder and decoder of this invention, although these will
`method and apparatus whereby an error correction
`not be described in great detail as they comprise ele
`scheme may be provided in which data bits are elimi
`ments which are standard in FEC implementations as
`nated to provide blocks of encoded data coding scheme
`well as interfaces to other boards of the TDMA system,
`without significantly weakening the error rate of the
`and a complete description may be found in the incor
`system.
`porated application.
`In order to achieve the objectives herein, the system
`DETAILED DESCRIPTION
`first incorporates an encoder which utilizes a
`rate
`convolutional encoder to encode the data and a supple
`It should be noted in reviewing this correction
`mentary coding system for converting the rate coded
`scheme that FIG. 1A shows a k=3 type encoder where
`data to a nominal rate. Thereafter, in order that the
`k is the number of taps on the shift register 14. Other
`encoded data fits within the fixed frame length which
`values for k can be used; but in this technology, k=3 is
`has been adopted as a standard for the present TDMA
`typically used for example purposes.
`transmission system, a portion of the excess data in each
`In the type of code being generated according to the
`frame of encoded data put out by the encoder must be
`present system, at the outputs I, Q from the encoder 14
`deleted or punched out. Preferably, these bits are
`the original data is no longer found in the data stream;
`spaced throughout the frame to minimize the effect of
`instead, a combination of several of the I, Q bits is used
`the punchout routine.
`to reassemble the original data. Since several I, Q bits
`It should be noted that the output of the encoder
`determine the value of each real data bit (when de
`contains more bits for representing each block of data
`coded), the effect of an error in transmission of any
`65
`than the input. Thus information about the actual state
`single I, Q bit is minimized. Therefore, a system such as
`of each input bit is represented in more than one output
`shown in FIG. 1 is used where each real, unencoded
`bit. Therefore, it is possible to punch out selected ones
`data bit of the incoming data stream 10 can be reassem
`
`60
`
`IPR2018-01474
`Apple Inc. EX1008 Page 8
`
`

`

`10
`
`15
`
`35
`
`4,908,827
`5
`6
`bled from the outgoing data streams 12, 13 by analysis
`The concept of seeking out the number of bits needed
`to reduce the length of the output data to the desired
`of a number of I and Q bits in the stream.
`block length, and preferably picking out those bits
`The IQ data is created using a shift register 14 com
`evenly spaced along the length of the data frame is an
`prising three stages 14 A, B, and C, and a pair of exclu
`entirely new approach not previously considered which
`sive OR gates 16, 18 which combine the bits present at
`significantly reduces the complexity of the decoding
`any given time in the shift register stages to form the IQ
`system as well as minimizing the likelihood of error in
`data streams 12, 13. This data stream is obviously rate
`code. That is the output data strings 12, 13 on the I, Q
`the decoded data.
`channels have twice as many bits as the input data 10, at
`An example of how to punch out the excess data bits
`follows from an understanding of the coding procedure.
`least for real data bits 10D-J.
`However, when a block of incoming data bits 10
`It is most desirable to punch out equal numbers of bits
`ends, e.g. at incoming bit 10D, the bit 10D will not be
`from each data channel so the blocks remain of equal
`fully encoded unless it is shifted at least to the last stage
`length. Also, both bits put out simultaneous on the I and
`14C of the shift register 14. In order to completely clear
`Q channels should not be punched out, as this will effec
`the shift register 14 and insure full encoding of each
`tively cause the loss of an instant in time.
`data bit, a number of known bits must be shifted in at the
`FIG. 2A illustrates an embodiment of this invention.
`The input data 10 enters the multiplexer 15. As long as
`end of the data block. These added or "tail' bits 10A, B,
`there is a valid input stream, the punchout control block
`C will usually be all O's. Thus in FIG. 1A we see an
`input bit stream of seven data bits D-J plus three excess
`17 will allow it to proceed. When the data input stream
`20
`generated tail bits A-C used to insure the full encoding
`is ended, the control block switches to the "B" input
`thus generating a sequence of zeros. Actually any se
`of these seven input data bits. "Generated' bits means
`that these are not part of the original data.
`quence will do so long as it is known to the decoder.
`The problem created by the fact that extra bits must
`The length of this tail sequence (illustrated in FIG. 1A
`be shifted in to clear the shift register (to fully encode
`as 10A, B, C) must be at least as long as one bit less than
`25
`the last input bits) is that excess output bits identified as
`the length of the shift register used in the convolutional
`encoder. It may be as long as desired beyond this
`the "tail data' of Channels I and Q result. Thus the
`encoded data no longer fits exactly into the block length
`length.
`r
`The resulting data block 10A-J (original desired plus
`to be transmitted. For example, to fully encode the last
`tail) then is encoded in the normal manner.
`two input bits, two additional shifts must occur in the
`shift register 14. This results in four excess output bits,
`The resulting bit stream is then clocked into a FIFO
`two in each of the I and Q channels. This causes the
`(first in first out) element 20 under the control of the
`punch out control unit 17. At certain predetermined bit
`actual code rate to be N/2N-2(k-1) where N equals
`positions no input (to the FIFO) clocking takes place.
`the number of input bits and k equals the constraint
`This effectively drops data from the bit stream resulting
`length of the encoder, i.e., the number of elements the
`shift register is divided into. As N approaches infinity,
`in the desired punching. The output bit streams are then
`the rate approaches , but always differs by the 20k-1)
`clocked out to be further processed or directed over the
`channel.
`COnStant.
`According to this invention, the solution to this prob
`If a second rate conversion puncturing is to take place
`lem of the presence of excess bits in the I, Q channels is
`(to be discussed below) it may take place either immedi
`40
`ately prior to or sometime following the FIFO opera
`to punch out selected channel bits, and treat them as
`erasures in the decoder at the receive side of the system.
`tIO.
`The decoder has a prior knowledge about all punc
`To review the example of FIG. 1A a rate code is
`being applied to L. bits of input 10 so that the output of
`turing that has taken place. It performs operations that
`are the logical inverse of those performed in the en
`the coder 14 is 2L channel bits on channels 12, 13. It is
`45
`absolutely necessary to generate that amount. How
`coder prior to the actual act of decoding the received
`ever, if every input bit is encoded an equal amount,
`reconstructed bit stream.
`when the last three bits of original data 10DEF are
`Specific details of block elements of the error correc
`tion system may be found in many references previously
`shifted into register 14, these three bits are left over, i.e.,
`published; for example, “Development of Variable Rate
`still in the shift register. Thus, if three more shifts are
`done to encode bits 10 DEF using as inputs dummy tail
`Viturbi Decoder and its Performance Characteristics,'
`pp. XII-24 through 30, Sixth International Conference
`bits 10 A,B,C, the number of bits encoded is now L-3.
`The last three bits coming in are dummy bits (and it is
`on Digital Satellite Communications, incorporated
`irrelevant what their state is); but these added bits had
`herein by reference.
`to be used to push the remaining data bits through the
`Books by Peterson and Welden, "Error Correction',
`shift register. The result is 20L-3) actual output bits in
`and "Principles of Digital Communication and Coding'
`data strings 12, 13, which amounts to six output bits too
`by Viturbi & Omura (McGraw-Hill) and Oppenheim's
`book on Digital Signal Processing are incorporated
`many as shown in FIG. 1. That is the basis of the prob
`len. Previous attempts to address this problem used an
`herein by reference for their discussion of trellis decod
`ing of coded data signals.
`approach which took the last three bits which were not
`60
`fully encoded, shifted, i.e. repeated them at the front of
`The tail punchout electronics of this invention has
`the incoming data block, and ran them into the encoder
`been designed for use in a system whose block transmis
`first. Thus, when the last three bits are in the shift regis
`sion length is further supported by a to rate transla
`ter, if does not matter that they are not fully encoded,
`tion. The basis for puncturing to go from a rate to a
`because they have previously been encoded at the front
`rate code is well known and extensively covered in
`of the data stream. However, the difficulty with this
`IEEE Transactions on Information Theory. Therefore
`approach applies in the complexity of the decoder
`only a discussion of the necessary electronics is given
`which just be used at the receive side of the system.
`below.
`
`50
`
`55
`
`65
`
`IPR2018-01474
`Apple Inc. EX1008 Page 9
`
`

`

`4,908,827
`7
`8
`Simply put, to achieve a rate decoder additional bits
`be selectively eliminated from either line of data in
`accordance with the pattern stored in the punchout
`must be deleted from each frame, i.e., in addition to the
`tail punch out bits. This is accomplished by initially
`ROM. By always punching out bits in the same location
`ignoring the four extra i.e., tail bits in the I and Q chan
`in each frame which is selected to have a punchout bit,
`nels, and converting the rate code to a rate code by 5
`a corresponding punch-in device 48b(FIG. 4) can be
`taking each group of six IQ bits as shown in the bottom
`provided in the decoder side of the system, and a flag bit
`of FIG, 1A, and deleting the last two of each set of
`can be set on the receive side of the transmission system.
`three bits in the I channel. Now only the first I bit and
`It should be noted that the FIFOs 32, 34 are provided
`all three Q bits remain. Looking again at the lower right
`solely for exercising punchout functions; without
`of FIG. 1A, it can be seen that to complete the conver- 10
`punching out the T bits, only the multiplexer would be
`sion, one more of the remaining four bits must be elimi
`necessary. The present system uses a 21 millisecond
`nated. In this case either the Ibit, or the associated Q bit
`frame and a 32 kilobit voice channel, meaning that each
`of the sole remaining complete pair must be deleted.
`frame comprises 672 bits. Thus, the output of multi
`plexer 20 must be reduced by 8 equally-spaced bits. In
`After the data is transmitted, when the data is reformed
`on the receiver side, an additional clock pulse is added 15
`such a system, the state counter and punchout ROM
`to denote the position of the deleted bit, and a flag bit is
`simply count to 448, which is 672X4/3+.
`provided on an associated control line to indicate that
`Specific bit locations are selected for punchout as
`the bit artificially created at the receiver in fact does not
`follows. Looking at FIGS. 1A and 1B, it can be seen
`convey any information about the data being transmit
`that since two of every three bits are already removed
`from one channel, only one bit remains eligible for
`ted.
`20
`In an alternative embodiment of this invention, using
`punchout in that channel out of each set of three bits.
`a constraint length k=5 encoder, with summing taps on
`However, if a bit, for example B3, is punched out in the
`the first, third and fifth positions of the encoder to de
`Q channel, then the bit B3 cannot be punched out from
`termine the polynomials which constitute the output
`the I channel or a complete increment of time is lost.
`data, the resulting of the multiplexer is a rate encoder. 25
`Thus, there is a certain relationship between the bits
`As a result, for L information bits coming in, a total of
`which must be punched out in the two channels I and Q.
`2L bits come out. As discussed above, it is actually
`The constraints which must be placed are that a corre
`20L--T), with T representing the extra bits that have to
`sponding bit in both the I and Q channel cannot be
`go into the tail. Using a K=5 encoder, the minimum
`punched out, and the bits punched out in each frame
`number of bits that T can be for the system is four. The 30
`should be separated as much as possible. Within these
`system (at the transmitter side) then does a bulk -rate to
`constraints, bits can be selected with the objective of
`-rate conversion. This is carried out in the rate con
`simplifying the design of the hardware. One further
`version plus tail punchout system of FIG. 2. Essentially,
`constraint is that bits cannot be removed in a sequence
`to go from the rate to rate, two of every set of six bits
`which constitutes a relative prime number to the way
`will be deleted, as shown at the bottom of FIG, 1A. The 35
`the bits were eliminated in the i-rate encoder.
`output of this system is
`2x(L-T) which is
`Turning to FIG. 3 which is a diagram illustrating
`4/3x(L-T). It is now necessary only to delete the few
`how the forward error correction system fits into the
`extra bits to eliminate the T factor. The actual number
`overall data transmission system, it can be seen that the
`of bits to be "punched out' is determined as follows.
`data from the TIP data bus which is the standard data
`Expanding the formula, the output of the rate conver- 40
`bus on the transmission side of a satellite communica
`sion system is 4/3L -- 4/3T. Only whole bits can be
`tion system feeds into the data bus 60 which in turns
`deleted; a fractional bit cannot. Therefore, T must be set
`feeds the data into a 56-word RAM 62. The reason for
`to be a number that is integrally divisible by three; fur
`the use of this RAM is that in decoding the data, the
`ther, the minimum number of bits to be deleted from the
`order of the data in each frame is reversed. Therefore,
`two lines is four. The smallest number over four that is 45
`in order to take this into account, the order in which the
`divisible by three is six; and the more bits deleted, the
`data is transmitted is reversed in this RAM 62. Obvi
`weaker the code. 4/3(T = 6) fixes the number of bits to
`ously, the timing for storing the data in this RAM as
`be deleted at eight bits. Therefore, eight bits must be
`well as for punching out the bits in the tail punchout
`punched out, preferably equally spaced through the
`section 32, 34 and for transmitting it in the I and Q
`length of the frame.
`50
`channels comes from a common timing source 64 such
`This is achieved in the circuit of FIG. 2B. It should be
`as is well known in the art and can be found in incorpo
`noted in reviewing the rate punchout device that in
`rated patents and applications. The signals to count data
`fact, the multiplexer 20 receives the inputs from both
`into the RAM and to clock the words are applied
`the I and Q data streams. The multiplexer effectively
`through the counter 66 and over the output 68 from this
`writes bits from the Q data stream over the I data stream 55
`counter 66 to the control lines of the RAM 62, as well
`5 of the time, so that of the bits in the I stream are
`as providing a common word clock line 70 to the paral
`eliminated. This is achieved under control of the punch
`lel-to-serial converter 72. This converter 72 operates on
`out ROM 22, which responds to the bit clock input 24
`the data stored in the RAM 62 and provides it serially to
`through state counter 26 to continuously track the posi
`the
`rate encoder 14 and then to the
`rate encoder
`tion of bits in each frame. In this way, bits are selec- 60
`which essentially comprises the mux 20 and punchout
`tively eliminated from a data stream to accomplish the
`ROM 22 and state counter 26, together with the tail
`to
`rate data conversion. Further, eight equally
`punchout FIFOs 32, 34. The output of the tail punchout
`spaced bits throughout the frame are selected for addi
`device 32, 34 is transmitted as timed by the AB signals
`tional deletion. The additional deletion is done through
`from the common timing section on line 80 through the
`the output of the punchout ROM 22 connected through 65
`interface 82.
`-
`gates 28 and 30 to the clock inputs of FIFO devices 32,
`In an advantageous modification which is made avail
`34. When the clock input is held low, then no output
`able by the design of the claimed invention, it is possible
`appears on the output line, with the result that a bit can
`to take data directly from the 56-word RAM 62 and
`
`IPR2018-01474
`Apple Inc. EX1008 Page 10
`
`

`

`O
`
`5
`
`25
`
`35
`
`4,908,827
`9
`10
`convey it over the bus 90 through an appropriate bypass
`occurs because of the use