Defence Science Journal, Vol 43, No 1, January 1993, pp 59-69
`© 1993, DESIDOC
`
`Coding Theory and its Applications in Communication Systems*
`
`Vijay K. Bhargava, Qing Yang and David J. Peterson
`Department of Electrical and Computer Engineering, University of Victoria
`PO Box 3055, Victoria, BC, Canada V8W 3P6.
`
`A"BSTRACT
`
`Error control coding has been used extensively in digital communication systems because of its
`cost-effectiveness in achieving efficient, reliable digital transmission. Coding now plays an important
`role in the design of modern communication systems. This paper reviews the development of basic
`coding theory and state-of-art coding techniques. The applications of coding to communication systems
`and future trends are also discussed.
`
`r---------------,
`
`III IIIIIIIIIII
`
`llISOl[ T( - - l
`[lATA OWKI.
`
`L
`
`.
`
`.__.J
`
`Figure 1. Digital communication using forward error control coding.
`
`can
`technique which
`design
`a
`is
`Coding
`fundamentally change
`the trade-offs
`in a digital
`communication system. The most
`trivial example of
`coding is the repetition of the same message on the
`transmission channel. Here it is clear that redundancy,
`and therefore reliability, is obtained at the expense of
`transmission efficiency, or bandwidth utilization.
`In
`general, error control coding can increase signal quality
`from problematic to acceptable levels. If the attendant
`
`1. INTRODUCTION
`
`1.1 The Coding Problem
`
`Error control coding is concerned with methods of
`delivering information from a source to a destination
`with a minimum of errors. Error control coding can be
`categorized as
`forward
`error
`correction (FEe),
`automatic repeat request (ARQ), or as a combination
`of FEC and ARQ (hybrid).
`
`The communication system depicted in Fig. 1
`employs FEe. The source generates data bits or
`messages that must be transmitted to a distant user over
`a noisy channel. Generally speaking, a specific signal
`is assigned to each of M possible messages that can be
`emitted by the source. The selection rule that assigns
`a transmitted signal to each message is the code. The
`encoder
`implements the selection rule, while the
`decoder performs the corresponding inverse mapping.
`Because of channel noise, the transmitted signals may
`not arrive at the receiver exactly as transmitted, causing
`errors to occur at the decoder input. A natural design
`objective is to select the code such that most of the
`errors occuring at the decoder input can be corrected
`by the decoder. thereby providing an acceptable level
`of reliabilty.
`
`Received 14 September 1992
`• Research supported by a grant
`Government of Canada.
`
`from Canadian Institute for Telecommunications Research under the NCE program of
`
`the
`
`59
`
`IPR2018-01474
`Apple Inc. EX1015 Page 1
`
`

`

`DEF SCI J, VOL 43, NO.
`
`JANUARY 1993
`
`increase in complexity at the transmitter and receiver
`is economically viable, and bandwidth utilization is not
`unduly
`compromised,
`useful
`perfo.rmance
`improvements may result. For example, with coding,
`less power may be required to communicate between
`a satellite and a mobile terminal. Furthermore, coding
`may result in an increase in the maximum number of
`mobile terminals per satellite
`The study of error control coding began in 1948with
`Claude Shannon) who demonstrated the existence of
`codes achieving reliable communication whenever the
`code rate is smaller than a threshold Ccalled the channel
`capacity. For
`the
`additive white Gaussian noise
`(AWGN).channel, the channel capacity is given by
`S]
`C = B log, L _ +
`r
`.N
`Where B is the channel bandwidth, and SIN is the
`ratio of signal
`to noise power
`falling within the
`bandwidth. This remarkable result indicates that the
`ultimate performance limit caused by channel noise is
`not reliability, as generally believed before Shannon's
`work, but
`the rate at which data can be reliably
`transmitted.
`The concept of channel capacity is fundamental to
`communication theory and is surprisingly powerful and
`general. It can be applied to a large class of channel
`models, whether memoryless or not, discrete or
`nondiscrete. However, Shannon's celebrated coding
`theorems are only existence theorems; they do not show
`how promising coding schemes can be constructed.
`Since the publication of Shannon's result, a considerable
`amount of
`research has addressed the design and
`analysis of practical coding and decoding techniques
`permitting reliable communication at
`the data rates
`promised by the theory 2-4.
`
`1.2 Basic Coding Process
`In addition to the FECIARQ categorisation
`mentioned earlier, coding systems have traditionally
`been
`separated
`into
`block
`and
`convolutional
`error-correction techniques.
`In an (n, k) linear block code, a sequence of k
`information bits is used to obtain a set of n-k parity
`bits, yielding an encoded block of n bits. Usually
`modulo-Z arithmetic is used to compute the parity bits.
`Modulo-Z arithmetic is particularly suited to digital
`logic; addition corresponds to the EXCLUSIVE-QR
`operation, while multiplication can be realised as an
`
`60
`
`AND operation. The code rate r is defined as r = kin
`where n is called the block length. Linear codes form
`a linear vector space;
`two code words can be added
`(modulo-Z) to produce a third code word.
`The Hamming weight of a code word c is defined
`to be the number of nonzero components of c. For
`example, the code word c =(110101) has a Hamming
`weight of 4. The Hamming distance between two code
`words c) and Cz, denoted d(ct , Cz), is the number of
`positions in which they differ. For example if c) =
`(110101) and Cz = (111000) then d(ct,Cz) = 3. The
`minimum distance d of a linear block code is defined
`to be the minimum \\ eight of its nonzero code words.
`A code can correct all patterns of t or fewer random
`errors and detect all patterns having no more than s
`errors, provided that s+2t+ 1 ~ d. If the code is used
`for error correction alone, any pattern of t or fewer
`random errors can be corrected, provided that 2t+ 1 ~ d.
`A convolutional code of rate l/v may be generated
`by a K stage shift register and v modulo-Z adders.
`Information bits are shifted in at the left, and for each
`information bit
`the output of the modulo-Z adders
`provides two channel bits. The constraint length of the
`code is defined as the number of shifts over which a
`single information bit can influence the encoder output.
`For the simple binary convolutional code, the constraint
`length is equal to K, the length of the shift register.
`Whether block coding or convolutional coding is
`used,
`the encoded sequence is mapped to suitable
`waveforms by the modulator and transmitted over the
`noisy channel. The physical channel or the waveform
`the hardware (for example,
`channel consists of all
`filtering and amplification devices) and the physical
`media that
`the waveform passes through, from the
`output of the modulator to the input of the demodulator.
`The demodulator estimates which of the possible
`symbols was transmitted based upon an observation of
`the received signal. Finally, the decoder estimates the
`information
`sequence
`from
`the
`transmitted
`demodulator output. The decoder makes use of the fact
`that the transmitted sequence is composed of the code
`words. Transmission errors are likely to result
`in
`reception of a noncode sequence.
`1.3 Coding Gain
`It is often useful to express coding performance not
`in terms of
`the error
`rate reduction for a given
`signal-to-noise ratio (SNR), but as the SNR difference
`at a fixed bit error rate. Consider an AWGN channel
`
`IPR2018-01474
`Apple Inc. EX1015 Page 2
`
`

`

`BHARGAVA. er a/ : CODING THEORY AND APPLICATIONS IN COMMUNICATION SYSTEMS
`
`with one-sided noise spectral density N 0 having no
`bandwidth restriction. Let Eb denote the received
`energy per bit. It can be shown that if the SNR EblNo
`exceeds -1.6 dB,
`there exists a coding scheme which
`error-free
`communications, while
`reliable
`allows
`communication is not generally possible at lower SNRs.
`On the other hand, it is well-known that the uncoded
`phase shift keying (PSK) modulation over the same
`channel requires about 9.6 dB to achieve a bit error
`rate of lO,5 . Thus, as shown in Fig. 2, a potential coding
`gain of 11.2 dB is theoretically possible.
`
`hardware and the much less significant decrease in the
`cost of analog components such as power amplifiers,
`antennas and so on.
`
`Practical communication systems rarely provide the
`ablity to make full use of the actual analog voltages of
`the received signal. The normal practice is to quantize
`these voltages. If binary quantization is used, we say
`that a hard decision is made at the receiver as to which
`level was actually sent. For example , in coherent PSK
`with equally likely transmitted symbols , the optimum
`threshold is zero. The demodulator output is a one or
`a zero depending on whether the voltage is above or
`below the threshold . With coding,
`it
`is desirable to
`maintain an indication of the reliability of this decision .
`A soft-decision demodulator first decides whether the
`voltage is above or below the decision threshold, and
`than computes a 'confidence' number which specifies
`how far from the decision threshold the demodulator
`output is. This number in theory could be an analog
`quantity , but in most practical applications a three-bit
`(eight-level) quantization is used. It is known that soft
`decision decoding is about 3 dB more efficient than
`hard decision decoding at very high EblNo. A figure of
`2 dB is more likely at realistic values of EJNo.
`
`2. CODING FOR DIGITAL COMMUNICAnONS
`
`2. Block Codes and their Decoding
`
`The basic idea behind all block codes is illustrated
`by the following example. We consider a binary code
`having the eight code words (ססOO00), (001101),
`(010011) , (011110), (100110) , (lOI011) , (llOI01) and
`(11lO00) . These codes words form a vector space of
`dimension three, so the code is a (6, 3) linear code .
`The minimum weight of the seven nonzero code words
`is 3, so the minimum distance is 3. Thus, the code is a
`single error correcting code . This code is said to be in
`three bits of any code word
`systematic form ; the first
`can be considered as message bits while the last three
`bits, which are uniquely determined by the first
`three
`bib. are the redundant or parit y bits.
`
`Many of the important block codes found to date
`are so-called cyclic codes or are closely related to cyclic
`codes. For such codes, if an n tuple c= ('1>, cJ , 0, .. . ,
`
`61
`
`_
`
`···i
`
`iiI
`
`it- !
`~!
`'I~ I i: ~
`! -' ~ I.... ~
`.... ~
`: ~ ~
`I~z I~~
`.~~ I ~ ;:)
`i~a
`Xd
`I~C
`I.... :5 I~g
`I u, a::
`: ~ t-
`
`a..~
`
`iII
`
`I
`·
`
`I
`
`!
`
`REGION OF POTENTIAL CODING GAIN
`
`10-
`
`'"
`~ 10-)
`a::
`I
`....
`iii
`
`~
`
`10-4
`
`10-5
`
`I
`- 2
`
`I
`0
`
`I
`2
`
`I
`4
`Eb"N o
`
`I
`6
`
`I
`8
`
`I
`10
`
`Figure 2. Performance of uncoded PSK over AWGN channel.
`
`Coding gain is defined as the difference in value of
`EblNo required to attain a particular error rate with and
`without coding. Notice that coding gain is obtained at
`the expense of transmission bandwidth . The bandwidth
`expansion is the reciprocal of the code rate . Coding
`schemes delivering 2 to R dB coding gain are widely
`used in modern digital communication systems . This is
`because of the phenomenal decrease in the cost of digital
`
`IPR2018-01474
`Apple Inc. EX1015 Page 3
`
`

`

`DEF SCI J, VOL 43, NO. I , JANUARY 1993
`
`Cn _ t is a code word, then the n tuple c'= (cn _t , Co, ct , •• . . ,
`cn - Z) , obtained by cyclically shifting c one place to the
`right , is also a code word. This class of codes can be
`easily encoded using simple feedback shift register
`circuits. Furthermore, because of
`their
`inherent
`algebraic structure,
`the decoding of cyclic code is
`straightforwarJ, both conceptually and in practice .
`Examples of cyclic and related codes include the
`Bose-Chaudhuri- Hocquenhem (BCH) , Reed-Solomon
`(RS) ,
`Hamming, maximum-length, maximum(cid:173)
`distance-separable (MDS), Reed -Muller, Golay , Fire,
`difference
`set,
`quadratic
`residue, Goppa,
`and
`quasicyclic
`codes. Some of
`these
`classes
`form
`overlapping sets. For example, RS code are a special
`class of BCH codes and also belong to the class of MDS
`codes. The details of these codes can be found in any
`one of the standard coding references 5-8.
`
`The first stc, of the decoding procedure involves
`re-encoding the received information bits to obtain a
`new parity sequence. The rnodulo-Z difference between
`this parity sequence and the original parity sequence is
`called the syndrome. If no errors have occurred, the
`parity bits computed at the decoder will be identical to
`those actually received, and the syndrome bits will be
`zero. If the syndrome bits are not zero, errors have
`been detected.
`
`the syndrome is processed
`For error correction,
`further. The algebraic constraints defining a given block
`code generally yield a decoding technique or algorithm
`for the code. The decoding algorithm makes further use
`of the syndrome to calculate the error pattern affecting
`the received word. Most decoding algorithms require
`the use of binary quantization (hard decisions) at the
`demodulator output. The syndrome is processed using
`anyone of the following methods:
`
`2.1.1 Table Look-Up Decoding
`
`k
`
`There is a unique correspondence between the 2 n
`-
`distinct syndromes and the correctable error patterns.
`redundancy n-k, all
`Thus,
`for codes with small
`correctable error patterns can be stored in a read-only
`memory (ROM), with the syndrome of the received
`word forming the ROM address. The error pattern is
`added modulo-Z to the received sequence to produce
`the transmitted code word . This procedure is used in '
`
`62
`
`some types of error correction hardware for computer
`memories.
`
`2.1.2 Algebraic Decoding
`
`The most prominent decoding method is the iterative
`algorithm for BCH codes due to Berlekamp. The basic
`idea is to compute the error-locator polynomial and
`solve for its roots. The complexity of this algorithm
`increases only as the square of the number of errors to
`be corrected. Thus, it is feasible to decode powerful
`codes. The use of Fourier-like transrorms has also been
`proposed to further reduce decoder complexity. The
`standard version of the algorithm is a bounded-distance
`algorithm. That is, not all possible error patterns can
`be corrected. The algorithm does not generalise easily
`to utilise soft decisions. There are several other
`algebraic decoding algorithms, some of which utilize
`soft decisions to improve performance. However,
`Berlekamp's algorithm is perhaps the deepest and most
`impressive result, and is straightforward to implement.
`This algorithm has permitted the use of BCH and
`Reed-Solomon codes in many applications, from the
`Voyager mission to compact disks.
`
`2.1.3 Majority Logic Decoding
`
`Majority logic decoding is a simple form of threshold
`decoding and
`is applicable
`to both
`block and
`convolutional codes . There are codes that, because of
`the special form of their parity check equations, are
`majority logic decodable. Reed-Muller codes are the
`most
`important class of codes of
`this
`type. A
`Reed-Muller code was used in the Mariner mission to
`encode photographs of Mars.
`
`2.2 Convolutional Codes and their DecoclinI
`Conovolutional
`codes
`have
`a much simpler
`mathematical structure than all but the most trivial block
`codes. Furthermore, unlike many block codes,
`it is
`possible to make use of soft- decision information in
`their decoding. For these reasons it is not surprising
`that
`they have been widely used. Because of the
`relatively small number of parameters specifying a
`convolutional code, many good codes have been found
`by computer
`search
`rather
`than
`by algebraic
`construction.
`The error-correction capability of a convolutional
`code is determined in most cases by the free distance
`
`IPR2018-01474
`Apple Inc. EX1015 Page 4
`
`

`

`BHARGAVA, et al : CODING TIfEORY AND APPLICATIONS IN COMMUNICATION SYSTEMS
`
`of the code. This is defined to be the minimum Hamming
`distance between any two semi-infinite code sequences
`generated by the encoder. By linearity, this is simply
`the minimum Hamming weight of any nonzero code
`sequence.
`
`Three major decoding methods for convolutional
`codes are briefly described in the following sections.
`
`2.2.1 Viterbi Decoding
`
`Viterbi decoding is presently the most widely used
`decoding technique for convolutional codes. The
`Viterbi
`decoding
`algorithm finds
`the most
`likely(maximum likelihood) transmitted code sequence
`by using a structure called a trellis", Each code sequence
`is represented by a path through the trellis . .The degree
`to which a given code sequence matches the noisy
`received sequence is measured in terms of a path metric.
`Paths with high path metrics correspond to the most
`sequences. The Viterbi
`likely
`transmitted
`code
`algorithm is an efficient technique for searching all
`possible paths to find the most likely transmitted code
`sequence. In fact, the algorithm applies to any trellis
`code, not just the convolution codes . The significance
`of the trellis viewpoint is that
`the transmitted code
`sequence almost always corresponds to the path with
`the highest path metric. A major advantage of the
`Viterbi algorithm is the ease with which soft-decision
`information may be incorporated into the path metric.
`Unfortunately, the complexity of the Viterbi algorithm
`has an exponential dependence on the code's constraint
`length K. In practice, the Veterbi algorithm is rarely
`used with codes having constraint lengths exceeding 7.
`Another point worth mentioning is
`that Viterbi
`decoding does not perform very well in a bursty channel ,
`making it necessary to use interleaving. Convolutional
`codes
`using
`the Viterbi
`algorithm are
`often
`concatenated with powerful block codes, especially in
`deep space applications.
`
`2.2.2 Sequential Decoding
`
`Again, code sequences are represented as paths in
`a trellis. Sequential decoding makes use of the fact that
`in most cases, there are only a small number of paths
`with high path metrics. Therefore, by carefully
`restricting the path search procedure, it is often possible
`to isolate the maximum likelihood path without keeping
`
`track of all possible paths. The complexity of sequential
`decoders is relatively independent of constraint length,
`so codes with large constraint lengths (up to 1(0) can
`be used, yielding large
`coding gains. Sequential
`decoding is more suitable than Viterbi decoding when
`low bit error rates « 10'5) are required. However,
`unlike
`the Viterbi
`algorithm,
`the
`procedure
`is
`suboptimum; only a small fraction of the Possible code
`sequences is examined at anyone time. The sequential
`decoder must be capable of detecting situations when
`the correct path is not in the set of sequences under
`examination and 'backtracking' to the point where the
`correct path was most
`likely lost. The decoder must
`then examine a different set of paths extending from
`that point. Several stages of backtracking may be
`necessary to find the correct path again. A major
`disadvantage of sequential decoding is that the number
`of computations is an ill-behaved random variable,
`necessitating a very large buffer. Consequently,
`performance is limited by the probability of the buffer
`overflow.
`
`2.2.3 Threshold Decoding
`
`Some convolutional codes are threshold decodable.
`Several parity checks may be calculated for each
`message bit and if they exceed a threshold, a decision
`on the correctness of the bit is made. Moderate values
`of coding gain (1-3 dB) can be obtained with relatively
`inexpensive
`decoders
`and
`limited
`amount
`of
`redundancy.
`
`2.3 ARQ and Hybrid FEe ARQ Schemes
`
`In an automatic repeat request (ARQ) scheme,
`whenever the receiver detects an error in the transmitted
`message, it sends a retransmission request to the trans(cid:173)
`mitter over a feedback channel. These requests are
`repeated until the message is received correctly. Three
`basic types of ARQ protocols are commonly used-stop(cid:173)
`and-wait, go-back-N, and selective-repeat 10-12.
`
`Because of its simplicity, ARQ is used in many data
`communications systems . However. the technique has
`a major shortcoming-the throughput efficiency may be
`highly dependent on channel conditions. At low SNRs,
`the number of retransmissions required for correct
`message transmission may be very large. Hence, a
`successful transmission may involve a very long time
`
`f\1
`
`IPR2018-01474
`Apple Inc. EX1015 Page 5
`
`

`

`DEF SCI J, VOL 43, NO.1, JANUARY 1993
`
`r - - - - - - - - - - - l FEEDBACK .....----:--
`CHANNEL
`
`--,
`
`r--------------------------~
`I
`I
`I
`~
`:
`i
`.
`
`DATA IN
`
`FEC
`ENCODER
`
`FORWARD
`CHANNEL
`
`I
`I
`I
`I
`
`DATA OUT
`ARQ. t---...;;.;...;.~~-
`I '---~
`
`I
`DECODER -r
`
`FEC
`
`~----------------
`BINARY FORWARD CHANNEL
`
`...J
`
`Figure 3. FEetARD hybrid error control coding system.
`
`delay. Of course, this behaviour is unacceptable for
`delay-sensitive applications such as the digital voice
`communications. One approach to reducing the time
`delay is the hybrid FEClARQ scheme (Fig. 3). Here
`an ARQ scheme is used to obtain a desired error rate.
`FEC coding is used to correct low-weight error patterns
`in each message, reducing the number of retransmission
`requests.
`
`In a type-I hybrid FEClARQ scheme, the message
`and error detecting parity bits generated by the ARQ
`system are further encoded with an FEC code". At the
`receiver,
`the error correction parity bits are used to
`correct channel errors. The FEC decoder produces an
`estimate of the message and the error detection parity
`bits. The result is then tested by the error detection
`system to determine if the message should be accepted
`as error-free, or rejected as containing errors. If the
`channel signal strength is poor (high bi~ error rate), or
`if the message is long,
`the probability of error-free
`these
`zero. Under
`transmission may
`approach
`conditions, the efficiency may be improved by using a
`than a simple ARQ
`type-I hybrid scheme rather
`protocol. However, if signal strength is adequate, the
`type-I hybrid scheme involves a waste of bandwidth;
`the error correction parity bits are unnecessary. Thus,
`a plot of data throughput versus signal strength exhibits
`a crossover point between standard ARQ and the type-I
`hybrid schemes.
`
`In a type-II hybrid FEC/ARQ scheme" the first
`transmission of a message is coded with error detection
`
`64
`
`parity bits alone, as in a standard ARQ protocol. If the
`receiver detects errors in the received block, it saves
`the erroneous block in a buffer and requests a
`retransmission. The retransmitted information is not
`the original coded message, but a block of parity bits
`derived by applying anFEC code to the message. The
`receiver uses these parity bits (which may themselves
`be in error) to correct the block stored in the receiver
`buffer. If error correction is not successful, subsequent
`retransmissions are requested, which may consist of the
`original codeword or another block of error correction
`parity bits. The retransmission format depends on the
`strategy and on the error correction code used. The
`intention of type-II hybrid schemes is to provide the
`standard ARQ under good channel
`efficiency of
`conditions
`while
`obtaining
`the
`performance
`improvement of type-I hybrid schemes under poor
`channel conditions:
`
`2.4 Rate-Adaptive Coding
`In order to cope with diverse system requirements
`and service options, it is very attractive to investigate
`rate-adaptive FEC protocols, in which the code rate is
`adapted to suit prevailing trans..mission conditions'f.
`Such
`a
`technique
`is
`applicable
`to
`satellite
`communication
`systems, where
`adaptive
`signal
`compensation may provide adequate performance
`temporary poor channel conditions (due to
`under
`rainfall, etc) without a permanent bandwidth reduction
`caused
`by
`excessive
`coding
`overhead
`In
`the
`rate-adaptive coding, a high rate code is used under
`good channel conditions to maintain a high information
`
`IPR2018-01474
`Apple Inc. EX1015 Page 6
`
`

`

`BHARGAVA, et aJ : CODING TIiEORY AND APPLICATIONS IN COMMUNICATION SYSTEMS
`
`rate . As the channel condition worsens , the information
`rate is reduced by applying lower rate codes to maintain
`the desired BER performance. It is possible to optimize
`service quality by applying rate-adaptive FEe coding.
`Traditionally, convolutional codes have only been used
`in low code rate applications. However, as data
`transmission rates increase , the need arises for good
`high rate convolutional codes with practical encoding
`and
`decoding
`techniques. High
`rate
`punctured
`convolutional
`codes
`are
`a
`significant
`recent
`development in which the difficulties usually associated
`with decoding high rate
`codes
`are
`significantly
`reduced":". Viterbi or sequential decoding of rate b/v
`punctured convolutional codes is no more complex than
`the decoding of rate l/v codes . In fact, the punctured
`code is obtained in a straightforward manner from a
`'parent' rate l/v code, while a Viterbi or sequential
`decoder for the latter code can be easily modified to
`decode the punctured code . This property makes
`punctured convolutional codes attractive for
`rate(cid:173)
`adaptive
`applications-a
`single
`decoder
`can
`accommodate the entire family of punctured codes
`arising from a single parent code.
`Among the class of block codes , maximum distance
`separable (MDS) codes are particularly well suited to
`rate-adaptaive coding techniques. An (n , k) code for
`which the minimum distance equals n-k+ 1 is called a
`MDS code. MDS codes are optimal in the sense that
`no (n, k) code has minimum Hamming distance
`exceeding n-k+ 1. The MDS codes most often
`encountered in practice are RS codes. RS codes are
`attractive not only because of the ease with which they
`can be decoded using Berlekamp's decoding algorithm,
`
`but also because they feature a wide variety of possible
`code rates and block lengths. Rate adaptivity arises in
`the following manner. A low rate parent RS code can
`be broken down into several high rate subcodes, in
`much the same way that a parent convolutional code
`yields high rate punctured codes . The subcodes are
`themselves linear block codes having the MDS property.
`With appropriate modifications,
`the decoder for the
`parent code can also be used to decode the subcodes.
`Thus a single decoder may be used in a rate adaptive
`system where the transmitter employs the subcode most
`suitable for the current channel state.
`
`3. CODING APPLICAnONS
`
`3.1 Comparison of Block and Convolutional Codes
`
`The comparison of block and convolutional codes
`presented here is applicable to an AWGN channel. For
`channels with memory such as a mobile fading channel,
`the benefits of coding are even more spectacular.
`The comparison is based on an uncoded binary PSK
`system employing coherent detection. The information
`rate of the coded systems under comparison is assumed
`to be fixed. The coded systems require more frequency
`bandwidth . Table 1 has been adopted from": Two bit
`error rates considered here are 10.5 and 10-8
`• The column
`labelled 'data rate capability'
`is taken to be the
`following: low « 10 kbps) , moderate (10 kbps to 1
`Mbps), high (1 to 20 Mbps) and very high (>20 Mbps).
`
`At moderate and high data rates, convolutional
`coding with Viterbi decoding appears ' v be the most
`attractive coding technique . This assumes that there is
`
`Table I : Comparboo of major coding techniques on an AWGN channel
`
`Coding technique
`
`Coding gain
`at IO-s
`(dB)
`
`Coding gain Data rate
`at 10-"
`capability
`(dB)
`
`Concatenated (RS and Viterbi)
`
`Sequential decoding (soft decision)
`
`Block codes (soft decision)
`
`Concatenated (RS and short block)
`
`Viterbi decoding (hard decision )
`
`Sequential decoding (hard decision)
`
`Block codes (hard decis ion)
`
`Block codes (threshold decoding)
`
`Convolutional codes (threshold decoding
`
`6.6-7.5
`
`6.0-7 .0
`
`5.0-6.0
`
`4.5-5.5
`
`4.0-5 .5
`
`4.0-5.0
`
`3.~ .0
`
`2 .~.0
`
`1.5-3.0
`
`8.5-9.5
`
`8.0-9.0
`
`6.5-7.5
`
`6.5-7.5
`
`5.0-6.5
`
`6.0-7.0
`
`4.5-5.5
`
`3.5-5.5
`
`2.5-4.0
`
`Moderate
`
`Moder ate
`
`Moderate
`
`Very high
`
`High
`
`High
`
`High
`
`High
`
`Very high
`
`65
`
`IPR2018-01474
`Apple Inc. EX1015 Page 7
`
`

`

`DEF SCI J, VOL 43, NO.1, JANUARY 1993
`
`no appreciable interference other than Gaussian noise,
`that a decoded bit error rate of 10-5 is satisfactory, and
`that long continuous bit streams are transmitted. As
`mentioned previously, one advantage of the Viterbi
`algorithm over algebraic block decoding algorithms is
`its ability to make use of soft-decision information.
`However, if efficient algorithms for decoding long block
`codes with soft decisions are developed,
`they will
`undoubtedly be quite competitive.
`At very high data rates, concatenated RS and short
`block code systems can provide roughly the same gain
`with less complexity than Viterbi decoding. For larger
`coding gains at high speeds, sequential decoding with
`hard decisions appears to be the most attractive choice.
`At moderate data rates a better case can be made for
`using sequential decoding with soft decisions. However,
`in situations where the system protocols require the
`transmission of blocks of data (such as TDMA), block
`codes appear to be more attractive.
`In many applications, concatenated coding" offers
`a substantial coding gain. Decoding errors typically
`manifest
`themselves as burst errors at
`the decoder
`output. These types of bursts can be corrected by
`superimposing an outer burst-error-correcting code,
`usually a RS code.
`The effect of using the two decoders, each combating
`a specific type of error, results in significant coding gain
`improvement. The inner decoder reduces poor quality
`data to medium quality data and the outer decoder
`reduces medium quality data to very good quality data.
`Long codes are often desirable for good error control
`regardless of channel characteristics, and concetenation
`is a practical way of creating efficient long codes.
`
`Another important factor to be taken into account
`is the hardware complexity of the error control coding
`system. For high- speed transmission systems, selection
`of the coding scheme is severely restricted by the scarcity
`of high-speed FEC decoders. Some typical error control
`coding techniques and associated decoder complexities
`are listed in Table 2.
`In practice, the selection of a coding scheme greatly
`depends on the data rate, the channel conditions, and
`implementation complexity. For example, block codes
`are better suited to applications requiring high data
`rates. A convolutional decoder would fail to keep up.
`However, for predominantly Gaussian channels,
`the
`convolutional codes tend to outperform most short
`block codes of
`interest. Most of
`the
`previous
`applications of FEC coding to digital communications
`involve convolutional codes. This is mainly because of
`technological difficulties of implementing decoders for
`powerful block codes. With recent developments in
`VLSI
`technology,
`the situation has changed. New
`technology and a demand for integrated packetised
`data/voice communications have made sophisticated
`block coding schemes increasingly attractive from an
`economic viewpoint.
`
`3.2 Applications to Satellite Communications.
`Two of the most
`treasured resources in satellite
`communications are power and bandwidth. Conserving
`these resources has been a major concern ever since
`information transmission via satellite became a reality.
`Error control coding often used to improve the
`transmission quality, which is otherwise compromised
`by interference and power limitations. Furthermore,
`because
`of
`the
`considerable
`propagation
`delay
`
`Table 2. Comlexity of typical error control coding techniques
`
`Type of error
`
`Coding technique
`
`Decoder complexity
`
`Convolutional codes with threshold decoding
`
`Low
`
`BCHcodes
`
`Random
`
`onvolutional codes with Viterbi decoding
`
`Convolutional codes with sequential decoding
`
`Burst
`
`Voncatenated (RS and Viterbi)
`
`ARQ with error detection only
`
`Fire codes
`
`Reed-Solomon codes
`
`Doubly codes Reed-Solomon codes
`Concatenated (RS and Viterbi) with interleaving
`
`High
`
`Low
`
`High
`
`66
`
`IPR2018-01474
`Apple Inc. EX1015 Page 8
`
`

`

`BHARGAVA. et aJ : CODING TIiEORY AND APPLICAnONS IN COMMUNICATION SYSTEMS
`
`in geostationary satellite links, FEC
`(250-300 ms)
`techniques tends to be more widely used than ARQ
`techniques, which require data retransmission.
`satellite
`One of
`the
`remarkable
`features of
`communication systems
`is
`that bit
`errors occurs
`randomly, which is considered to be a significant
`advantage when applying FEC codes. A recent trend
`in digital satellite communication systems is to employ
`powerful FEC codes with large coding gains, making
`efficient use of limited satellite resources'", Since the
`usable frequency bands are severely limited, it is also
`desirable to apply high rate FEC codes.
`In satellite communication systems, convolutional
`codes with constraint length 7 are widely used. Block
`codes are also applied in some satellite systems .
`Examples of using block codes include a (31, 15) RS
`code for
`the joint
`tactical
`information distribution
`system (mDS), a (127, 112) BeH code for
`the
`INTELSAT V system, and a (7, 2) RS code for the air
`force
`satellite
`communications
`(AFSATCOM)
`wideband channels.
`Heavy signal attenuation is occasionally experienced
`in satellite channels due to