Umted States Patent
`
`[19]
`
`[11] Patent Number:
`
`5,734,962
`
`
`Hladik et a1.
`[45] Date of Patent:
`Mar. 31, 1998
`
`USOOS734962A
`
`[54] SATELLITE COMMUNICATIONS SYSTEM
`Egg-(111%?G PARALLEL CONCATENATED
`
`[75]
`
`Inventors: Stephen Michael Hladik, Albany, N.Y.;
`William Alan Check; Brian James
`Glinsman, both of Hemdon, Va.;
`Robert Fleming Fleming, 111,
`Derwood, Md.
`
`[73] Assignee: General Electric Company,
`Schenectady, NY.
`
`FOREIGN PATENT DOCUMENTS
`B-13079/92
`9/1992 Australia ................................. 371/46
`OTHER PUBLICATIONS
`
`“Optimal Decoding of Linear Codes for Minimizing Symbol
`Error Rate”, by Bahl, Cocke, Ielinek & Raviv, IEEE Trans-
`actions on Information Theory, pp. 284—287, Mar. 1974.
`“Decision Depths of Convolutional Codes”, by Anderson &
`Balachandran, IEEE Transactions on Information, vol. 35,
`No. 2, pp. 455—459, Mar. 1989.
`“An Algorithmic Approach", by Anderson and Mohan, pp.
`216 and 336—342.
`
`Primary Examiner—Reinhard J. Eisenzopf
`[21] App1' No.: 684’276
`Assistant Examiner—Thanh Le
`[22] Filed:
`Jul. 17, 1996
`Attorney, Agent, or Firm—Jill M. Breedlove
`H0413 7/185
`[51]
`Int. Cl 6
`[57]
`ABSTRACT
`........................... 455/12.1; 455/21; 370/342;
`[52] US. Cl.
`A VSAT satellite communications network utilizes parallel
`371/374; 371/43; 375/200
`_
`concatenated coding on its inbound or outbound links, 01.
`[58] Field of Search .................................. 455/121, 13.1,
`both. For short data blocks, nonrecursive systematic tail-
`”(55/132, 13'3” 19’ 209 21* 427’ 428’ 4303
`biting convolutional codes are used. For longer data blocks,
`73 ’ 370/316’ 320’ 342’ 593’ 513’ 514’ 515’
`recursive systematic convolutional codes are used. These
`375/2007 205’ 371/374, 43! 46
`parallel concatenated coding techniques are used in con-
`.
`junction with spread—spectrum modulation to provide a
`References Clted
`VSAT communications system which meets FCC regula—
`U.S_ PATENT DOCUMENTS
`tions on the total power spectral density of transmitted
`455,121
`4/1989 B
`
`signals as Well as mitigates interference from adjacent
`.
`aran .....................................
`3,733,331....
`2513;; Le.
`
`
`. 371/374
`5/1995 Khaled et a1.
`........................... 455/121
`4/1997 Rosen et a1.
`
`I
`
`[56]
`
`R 32 905
`e.
`,
`2:233:22:
`5,416,804
`5,625,624
`
`12 Claims, 4 Drawing Sheets
`
`SATELLITE
`
`
`
`
`DOWN LINK
`
`SIGNAL
`
`UPLINK
`
`SIGNAL
`
`PACKET-T0
`
`
`CODEWOFID
`
`CONVERTER
`
`
`
`ERICSSON EXHIBIT 101 1
`
`

`

`US. Patent
`
`Mar. 31, 1998
`
`Sheet 1 of 4
`
`5,734,962
`
`m.._._1_._m._.<m
`
`v_z_u_n5
`
`J_<20_m
`
`Z>>OD
`
`mmhmm>200
`
`O._..l_.m_x0<n_
`
`Dm0>>m000
`
`ENEm>zOO
`
`Ema—00mm_
`
`XZEZ>>OD
`
`.2205
`
`
`NOW—30m
`
`
`
`

`

`US. Patent
`
`Mar. 31, 1998
`
`Sheet 2 of 4
`
`5,734,962
`
`Z>>OD
`
`Emkmm>ZOO
`
`a..uamt—4mm..mm
`
`Mu.
`
`EOF<ADDOEmQ
`
`#2onmm>mowmm"_m10:26..2069
`Iobmxoi¢53805
`
`
`mOmmeOr—m
`
`
`
`4w22<IOmmtgmzfiuh
`
`IauE
`
`
`
`wkmmEmSzoommzwmuzooB”N.5
`
`E«.9538:
`H358
`
`
`
`mmtémo”.mmooozm
`
`
`
`
`
` $.onlcomImm5880?.._mzz<xommEsmz<EE
`
`mmflJOmhzOO
`
`>m0_2m=2N.me.Vmm
`
`._<Z_2mm._.m3:
`
`
`
`
`
`mOmmMOOmn.AwZZ<IOIm>_m0wm
`
`
`
`
`
`
`
`
`

`

`US. Patent
`
`Mar. 31, 1998
`
`Sheet 3 of 4
`
`5,734,962
`
`$053305.oh
`
`
`
`Emtszmou.$.on<_>V
`
`mmo
`
`omozmooo
`
`mmtgmo“.
`
`uuw
`
`ozEEozEmooo_2:a:FIIIIIIIIIIIIIIL
`_.,:..--H__a......._\\\n‘l.
`
`
`
`mmDOOzwm._m<_>_s_<m00mn_
`
`.856m20EM.“Q.50.5<29
`
`72
`
`on0$9.30
`
`mmooozm
`
`
`
`
`
`

`

`US. Patent
`
`Mar. 31, 1998
`
`Sheet 4 of 4
`
`5,734,962
`
`c:L\V
`
`mm
`
`_._.
`
`mm><m._mm._.z_rENDOOMOP
`
`0WWmmo
`
`
`
` _IIIIIIIIIIIJ_:2:u“ozEEozanmo__maoo_rllllllllllll_
`
`.\NE
`
`mm
`
`ZO_m_0wD-._.n_Om
`
`ZO_H<EEOH.Z_
`
`mDOOmmzz.wom._n=>:mm0“.
`mm><m4mwhzmoImw><m._mm:.2_woINDOOMD
`
`m:.
`
`coon.m8
`
`zo_m_0ma-h_0ma:
`
`20.2582.w:
`
`OAOIwwmIF
`
`
`
` ow0_>moZO_m_0mov:
`
`
`
`VJMNKImmooomomgm<§2<m00ma
`
`wow
`
`
`
`MDOOEms—.30
`
`awn—002m
`
`mmEmSzoo
`
`w:
`
`
`
`ZO_._.<_2mOu_z_QMDOOMQ
`
`
`
`
`
`wOOOIwzz_m0”.XOOAm
`
`
`
`
`
`XOOJmZOF<S_m_Ou_Z_Dun—00mm
`
`
`
`._.Dn_._.DOZO_m_Omn_..EOm
`
`wQOOmwzz_m0“.
`
`
`
`
`
`MQOOQw._.<zm._.<OZOOmmEmwm0”.
`
`mmEmSzoo
`
`
`mNEw><mjmmhz_Imooowo
`$0380A
`Fzmzfiwmzooo5$95300
`358200Fmobnzoozmo
`3033009.5105<5
`
`
`
`.205i206
`
`
`
`
`
`

`

`1
`SATELLITE COMMUNICATIONS SYSTEM
`UTILIZING PARALLEL CONCATENATED
`CODING
`
`FIELD OF THE INVENTION
`
`The present invention relates generally to satellite com—
`munications systems and, more particularly, to a very small
`aperture terminal satellite communications system employ-
`ing parallel concatenated coding on its inbound or outbound
`links, or both.
`
`BACKGROUND OF THE INVENTION
`
`There is an emerging market for multi—media communi—
`cations via satellite using low-cost, very small aperture
`terminals (VSAT’s). Advantages of utilizing a smaller
`antenna than is currently the general practice in the industry
`today include a reduced reflector cost, lower shipping costs,
`reduced mounting hardware and labor, and greater customer
`acceptance due to a less obtrusive appearance. However, the
`use of a smaller-aperture dish antenna can cause an unde-
`sirable reduction in network capacity. This is due to several
`causes related to the reduced antenna size: (1) decreased
`received and transmitted signal power caused by the asso-
`ciated decrease in antenna gain; and (2) Federal Communi—
`cations Commission (FCC) regulations limiting the power
`transmitted by a VSAT utilizing an antenna smaller than a
`specified size in order to limit the interfering power flux
`density at adjacent satellite orbital slots. The use of a VSAT
`power amplifier with the same or less power output in order
`to reduce VSAT cost further contributes to the decrease in
`network capacity due to power limitations.
`Unfortunately, it is diflicult to obtain the desired large
`coding gain on short data blocks (that are typical of some
`types of VSAT transmissions) to solve these problems with
`the required bandwidth efficiency and decoder complexity
`using conventional coding techniques.
`Accordingly, it is desirable to provide a satellite commu-
`nications system that
`increases network capacity when
`VSPII" s with reduced antenna apertures are used by decreas-
`ing the required energy—per—bit—to-noise power-spectral-
`density ratio Eb/N, with spectrally efficient techniques.
`SIJMIVIARY OF THE INVENTION
`
`In accordance with the present invention, a VSAT satellite
`communications network utilizes parallel concatenated cod-
`ing on its inbound or outbound links, or both. In one
`embodiment, for short data blocks that are typical of packet
`transmissions, credit card transactions, and compressed
`voice communications, nonrecursive systematic tail—biting
`convolutional codes are used as the component codes in
`such a parallel concatenated coding scheme. For longer data
`blocks that are typical of file transmission, the VSAT and
`network’s hub terminal utilize recursive systematic convo-
`lutional codes.
`
`In a preferred embodiment, the aforementioned parallel
`concatenated coding techniques are used in conjunction with
`spread-spectrum modulation, resulting in a system which
`meets FCC regulations on the total power spectral density of
`transmitted signals and mitigates interference from adjacent
`satellites.
`
`BRIEF DESCRIPTION OF THE DRAWINGS
`
`10
`
`15
`
`20
`
`25
`
`30
`
`35
`
`45
`
`50
`
`55
`
`The features and advantages of the present invention will
`become apparent from the following detailed description of
`the invention when read with the accompanying drawings in
`which:
`
`65
`
`5 ,734,962
`
`2
`
`FIG. 1 is a simplified block diagram illustrating a VSAT
`communications system employing parallel concatenated
`coding in accordance with the present invention;
`FIG. 2 is a simplified block diagram illustrating a VSAT
`satellite communications system’s hub terminal employing
`parallel concatenated coding according to the present inven-
`tion;
`FIG. 3 is a simplified block diagram illustrating a pro-
`grammable encoder useful in a VSAT communications sys-
`tem according to the present invention; and
`FIG. 4 is a simplified block diagram illustrating a pro-
`grammable decoder useful in a VSAT communications sys—
`tem according to the present invention.
`DETAILED DESCRIPTION OF THE
`INVENTION
`
`The invention described herein is a VSAT satellite com-
`munications system utilizing parallel concatenated coding
`techniques involving, for example, parallel concatenated
`tail—biting convolutional codes and parallel concatenated
`recursive systematic convolutional codes (i.e., so-called
`“turbo codes”), and their respective decoders. In particular,
`for parallel concatenated tail-biting convolutional codes, a
`decoder comprising circular MAP decoding is employed,
`such as described in commonly assigned, copending US.
`patent application Ser. No. 08/636,742 of Stephen M. Hladik
`and John B. Anderson, filed Apr. 19, 1996 and incorporated
`by reference herein.
`Parallel concatenated coding is used on the inbound—link
`transmissions (VSPIF—to—hub) or outbound—link transmis—
`sions (hub-to—VSAT) or both links of a VSAT satellite
`communications network. In addition, parallel concatenated
`coding can be utilized to provide error correction/detection
`coding for direct peer-to—peer (VSA'I‘—to-VSAT) transmis—
`sions. In one embodiment, for short data blocks that are
`typical of packet transmissions, credit card transactions, and
`compressed voice communications, nonrecursive systematic
`tail—biting convolutional codes are used as the component
`codes in a parallel concatenated coding scheme. For longer
`data blocks that are typical of file transmission, parallel
`concatenated coding comprising recursive systematic con-
`volutional codes is utilized by the VSAT’s and the network’s
`hub terminal.
`
`In accordance with the present invention, the use of these
`parallel concatenated coding techniques in conjunction with
`spread-spectrum modulation provides a very efiective solu-
`tion to facilitate compliance with the aforementioned FCC
`regulations on adjacent satellite interference by decreasing
`the required effective radiated power (ERP) and the power
`spectral density of the transmitted signal. In addition, this
`combination mitigates interference from adjacent satellites.
`FIG. 1 is a block diagram of a VSAT satellite communi—
`cations system that employs parallel concatenated coding in
`accordance with the present invention. This system funda-
`mentally comprises a number of VSAT terminals 10, a
`satellite 12 with a communications transponder, and possi-
`bly a hub terminal 14. Communication within the VSAT
`network may be either one-way or two-way and may travel
`in a variety of paths: (1) VSAT—to—VSAT directly (i.e., mesh
`connectivity) and (2) VSM—to-hub—terminal and/or hub-
`terminal—to-VSAT (i.e., star connectivity).
`As shown in FIG. 1, a VSAT terminal 10 comprises
`transmitter signal processing 20, receiver signal processing
`22 and an antenna 24. In accordance with the invention
`described herein, the VSAI’s transmitter signal processing
`comprises the following: an input port 25 for accepting data
`
`

`

`5,734,962
`
`3
`from an information source 26; an encoder 28 that applies a
`parallel concatenated code to blocks of data bits received
`from the source; a packet formatter 30 for generating a data
`packet (comprising one or more codewords from encoder
`28). a synchronization bit pattern and control signaling bits;
`a modulator 32', an up—converter 34 for translating the
`modulated signal to the carrier frequency; a power amplifier
`36; and connection to antenna 24 via an appropriate inter-
`face (e.g., a switch or filter duplexer). The VSAT’s receiver
`signal processing comprises: a low-noise amplifier 40, a
`down—converter 42 for translating the received signal from
`the carrier frequency to an intermediate frequency, a
`demodulator 44 for synchronization and demodulation, a
`packet-to-codeword formatter 46, a decoder 48 suitable for
`the parallel concatenated code utilized by the transmitter,
`and an output port 49 for transferring received messages
`(i.e., blocks of data bits) to an information sink 50. For
`Inevity, a detailed block diagram is only shown for one
`VSAT in FIG. 1.
`
`The synchronization functions performed by demodulator
`44 include carrier frequency synchronization, frame
`synchronization, symbol synchronization. and, if needed.
`carrier phase synchronization. Symbol synchronization is
`the process of estimating the best sampling time (i.e., the
`symbol epoch) for the demodulator output in order to
`minimize the probability of a symbol decision error. Frame
`synchronization is the process of estimating the symbol
`epoch for the first symbol in a received data frame (for
`continuous transmissions) or packet (for discontinuous
`transmissions),
`For the case in which spread spectrum signals are trans-
`mitted by the VSAT, the VSAT modulator shown in FIG. 1
`includes the spreading function; and the VSAT demodulator
`shown in FIG. 1 includes the despreading function. Spread
`spectrum techniques increase the signal bandwidth relative
`to the bandwidth of the modulated data signal by imposing
`a spreading signal comprising chips (in the case of direct
`sequence spread spectrum) or hops (in the case of frequency
`hopping spread spectrum) that are pseudorandom and inde-
`pendent of the data signal. In direct sequence spread
`spectrum, the data signal is multiplied by a signal that
`corresponds to a pseudorandom sequence of chips having
`the values of +1 or —1. The duration of the chip pulses is less
`than the symbol interval of the modulated data signal; hence,
`the resulting signal’s bandwidth is greater than that of the
`original modulated signal. In frequency hopping spread
`spectrum, the carrier frequency of the modulated signal is
`changed periodically according to a pseudorandom pattern.
`Again, the bandwidth of the spread signal is greater than that
`of the original modulated signal.
`Despreading in the demodulator is the process of remov-
`ing the spreading from the received signal. Typically, the
`demodulator correlates the received signal with a replica of
`the spreading waveform to despread a direct sequence
`spread spectrum signal, while in a frequency hopping spread
`spectrum system. it hops the frequency of an oscillator in the
`receiver’s down converter using the same pattern employed
`by the transmitting terminal to despread a frequency hopped
`spread spectrum signal. Typically, a filter is applied to the
`received signal after despreading to attenuate wide-band
`noise and interference components in the recovered signal.
`Ablock diagram of the hub terminal is presented in FIG.
`2. In accordance with the invention described herein. it
`comprises: input ports 51 for accepting data from one or
`more information sources 52', output ports 53 for transfer-
`ring received messages (i.e., blocks of data bits) to one or
`more information sinks 54; a bank of transmitter channel
`
`4
`processors 56; a bank of receiver channel processors 58; a
`switch 60 for connecting each active source to a transmitter
`channel processor and for connecting each active receiver
`channel processor to the appropriate information sink or a
`transmitter channel processor; a memory 62; a controller 64
`for controlling the flow of data through the switch; a
`combiner 66 for combining the signals generated by each
`transmitter channel processor into one signal; an
`up-converter 68 for translating the combined signals to the
`carrier frequency; a power amplifier 70 connected to the
`antenna via an appropriate interface (e.g., a switch or filter
`duplexer); an antenna 72; a low—noise amplifier 74 that is
`coupled to the antenna via the aforementioned interface; a
`down-converter 76 for translating the received signal from
`the carrier frequency to an intermediate frequency (IF); and
`a signal splitter 78 for providing the IF received signal or
`possibly a filtered version of the IF received signal to the
`bank of receiver channel processors.
`The transmitter channel processor shown in FIG. 2 com-
`prises: an encoder 80 that applies a parallel concatenated
`code to blocks of data bits received from a source; a packet
`formatter 82 for generating a data packet (comprising one or
`more codewords from encoder 80). a synchronization bit
`pattern and control signaling bits; and a modulator 84. As
`with the VSAT, the hub’s modulators include the spreading
`function for the case in which spread spectrum signals are
`transmitted by the hub. The receiver channel processor of
`FIG. 2 comprises a demodulator 86, a packet—to—codeword
`converter 88 for selecting samples from the demodulator
`output to form the received codewords that are inputted to a
`decoder for parallel concatenated codes, and a decoder 90
`suitable for the parallel concatenated code utilized by the
`transmitter. The hub’s demodulators include several func-
`tions: synchronization, demodulation, and, for the case in
`which the hub receives spread spectrum signals, despread-
`ing.
`One function of the hub’s memory is to temporarily store
`data received from the information sources or receiver
`channel processors in the event that all transmitter channel
`processors or output ports are busy when a message arrives
`at switch 60. The memory also stores necessary network
`configuration parameters and operational data.
`In one alternative embodiment of the present invention,
`an outer code is used in series concatenation with the (inner)
`parallel concatenated code (PCC); an associated outer
`decoder is also connected in series concatenation with the
`decoder for the inner PCC.
`
`Additionally, a flexible, programmable encoder/decoder
`system may be utilized by the VSAT and hub equipment for
`implementing several options:
`(1) parallel concatenated coding as described herein-
`above;
`(2) an outer code in series concatenation with an inner
`parallel concatenated code (PCC) as described herein-
`above;
`(3) serial concatenated coding comprising an outer
`encoder and only one component encoder of a PCC
`encoder;
`(4) a conventional convolutional code or block code alone
`(i.e., without series or parallel concatenation).
`FIG. 3 illustrates a block diagram of a flexible, program—
`mable encoder that implements these four coding options.
`,As shown. the flexible, programmable encoder comprises an
`encoder 100 for parallel concatenated codes, an encoder 102
`for an outer code, and five switches Sl—SS. Encoder 100 for
`parallel concatenated codes comprises N encoders, N—l
`
`10
`
`15
`
`20
`
`25
`
`30
`
`35
`
`40
`
`45
`
`50
`
`55
`
`65
`
`

`

`5,734,962
`
`5
`interleavers, and a codeword formatter 106. Table I as
`follows summarizes the switch positions for various modes
`of encoder operation.
`
`TABLEI
`
`Switch Positions
`
`Mode
`SI
`82
`SS
`S4
`SS
`
`O
`
`0 CLOSED 0
`0
`(1)PCCC
`CLOSED D
`1
`1
`(2) Serial concatenation with inner PCC
`OPEN
`1
`11
`(3) Standard serial concatenation
`l
`OPEN
`1
`00
`(4) Single code
`
`
`O1
`
`FIG. 4 is a block diagram of a flexible, programmable
`decoder that implements the decoders for the four encoder
`modes presented hereinabove. This programmable compos-
`ite decoder comprises a decoder 110 for parallel concat-
`enated codes, a threshold decision device 112 for imple-
`menting a decision role, a decoder 114 for an outer code, and
`six switches Sl—S6. Assuming that the output of decoder 110
`is the probability that the value of the decoded bit equals
`zero, an exemplary decision rule is: If the output is greater
`than 1/2, then decide that the decoded bit is zero; if less than
`1/2, then assign the value one; if equal to 1/2, then arbitrarily
`assign a value.
`Decoder 110 for parallel concatenated codes further com-
`prises a composite codeword to component codeword con—
`verter 116. N component decoders, N— 1 interleavers and two
`identical deinterleavers 118. Each deinterleaver has a reor-
`dering function that returns a sequence of data elements that
`have been permuted by the N—l interleavers connected in
`series to their original order. Table II as follows summarizes
`the switch positions for various modes of decoder operation.
`(In the table, X denotes the “don’t care” condition, i.e., the
`switch may be in either position.)
`
`TABLE 11
`
`Switch Positions
`
`Mode
`51
`52
`S3
`S4 SS
`86
`
`
`0 CLOSED O
`0 CLOSED 0
`
`1
`
`OPEN
`
`1
`
`(1) FCC
`(2) Serial
`concatenation
`with inner PCC
`(3) Standard serial
`concatenation
`
`O
`0
`
`1
`
`0
`0
`
`1
`
`X
`0 for hard-decision
`decoding; 1 for soft-
`decision decoding
`D for hard—decision
`decoding; 1 for soft-
`decision decoding
`1 1OPEN11(4) Single code X
`
`
`
`
`
`6
`that in Mode 3 or Mode 4, encoder switches S4 and SS and
`decoder switches 81 and 82 are all set to position 0.
`Therefore, FIGS. 3 and 4 show puncturing unit 140 and
`depuncturing unit 142, respectively, in phantom for imple—
`menting these puncturing and depuncturing functions,
`respectively, when a punctured convolutional code is used in
`Mode 3 or Mode 4.
`In a preferred embodiment of this invention, convolu—
`tional codes are used as the component codes in an inner
`parallel concatenated code, and a block code (e.g., at Reed—
`Solomon code or BCH code) is used as an outer code in
`serial concatenation.
`
`In a preferred embodiment in which spread spectrum
`signals are transmitted by the VSAT’s, a random channel
`access protocol such as ALOHA is used in conjunction with
`code division multiple access. The hub receiver utilizes a
`number of demodulators for each spreading code in order to
`receive time—overlapping signals that utilize time-delayed
`versions of the same spreading sequence. Each demodulator
`for a given spreading sequence demodulates a signal using
`a different time shift of that spreading sequence.
`Also in a preferred embodiment, one or more spreading
`sequences are reserved for use by VSAT’s over specified
`periods of time on an assigned basis in order to provide
`higher-quality channels with greater throughput. Reserva—
`tion requests fi'om the VSAT’s and assignments are pro-
`cessed by a network controller that is connected to a hub
`terminal.
`
`In a preferred embodiment that utilizes spread spectrum
`signals and the programmable encoder and decoder
`described hereinabove, the system associates a given spread—
`ing sequence with a particular error correcting code to allow
`different signals to utilize difierent error correcting codes
`simultaneously. Since each detected signal’s spreading
`sequence is identified by a corresponding demodulator, the
`receiver can appropriately configure the programmable
`decoder for each detected signal. This mode of network
`operation is useful for simultaneously supporting several
`applications having difierent error correction coding
`requirements without the need for additional control signal-
`mg.
`A circular MAP decoder useful as the component decod—
`ers in FIG. 4 is described in commonly assigned, copending
`US. patent application Ser. No. 08/636,742. The circular
`MAP decoder can deliver both an estimate of the encoded
`data block and reliability information to a data sink, e.g., a
`speech synthesis signal processor for use in transmission
`error concealment or protocol processor for packet data as a
`measure of block error probability for use in repeat request
`decisions. As described in commonly assigned, copending
`U.S. patent application Ser. No. 08/636,732 of Stephen M.
`Hladik and John B. Anderson, filed Apr. 19, 1996 and
`incorporated by reference herein, the circular MAP decoder
`is useful for decoding tail—biting convolutional codes, par-
`ticularly when they are used as component codes in a
`parallel concatenated coding scheme.
`A circular MAP decoder for error-correcting trellis codes
`that employ tail biting according to US. patent application
`Ser. No. 08/636,742 produces soft—decision outputs. The
`circular MAP decoder provides an estimate of the probabili-
`ties of the states in the first stage of the trellis, which
`probabilities replace the a priori knowledge of the starting
`state in a conventional MAP decoder. The circular MAP
`decoder provides the initial state probability distribution in
`either of two ways. The first involves a solution to an
`eigenvalue problem for which the resulting eigenvector is
`the desired initial state probability distribution; with knowl—
`
`10
`
`15
`
`20
`
`25
`
`3O
`
`35
`
`45
`
`50
`
`55
`
`65
`
`
`
`
`
`
`
`
`
`tail—
`The VSAT’s utilize diiferent codes (e.g., PCCC,
`biting PCCC, recursive systematic convolutional, nonrecur—
`sive systematic convolutional, block codes) in different
`combinations (e.g., modes 1, 2, 3, and 4), depending on the
`communication application and required transmission rates.
`When convolutional codes are utilized in any of the
`modes described hereinabove, the programmable encoder of
`FIG. 3 may also include puncturing via a known pattern to
`increase the rate of the resulting code, and the programmable
`decoder of FIG. 4 may also include the associated depunc—
`turing function. When punctured convolutional codes are
`used as the component codes in parallel concatenated
`coding, the codeword forrnatter of FIG. 3 deletes code bits
`from the component codewords according to the desired
`puncturing patterns. In this case, the PCC decoder’s com-
`posite codeword to component codeword converter inserts
`neutral values for the punctured bits in the component
`codewords that it outputs to the component decoders. Note
`
`

`

`7
`
`5 ,734,962
`
`8
`, [3b1 by the backward recursion:
`
`(ii) Calculate [31,
`
`.
`
`.
`
`BFrH-IBH-lr fiL—l, »
`
`.
`
`.
`
`.
`
`,1.
`
`edge of the starting state, the circular MAP decoder performs
`the rest of the decoding according to the conventional MAP
`decoding algorithm. The second is based on a recursion for
`which the iterations converge to a starting state distribution.
`After sufficient iterations. a state on the circular sequence of
`states is known with high probability, and the circular IVLAP
`decoder performs the rest of the decoding according to the
`conventional MAP decoding algorithm which is set forth in
`“Optimal Decoding of Linear Codes for Minimizing Symbol
`Error Rate.” by Bahl. Cocke. Jelinek and Raviv. IEEE
`Transactions on Information Theory, pp. 284—287, Mar.
`1974.
`The objective of the conventional MAP decoding algo-
`rithm is to find the conditional probabilities:
`
`P{mar m at time t/receive channel output: y“ .
`
`.
`
`. ,yL}.
`
`The term L in this expression represents the length of the
`data block in units of the number of encoder symbols. (The
`encoder for an (n. k) code operates on k—bit input symbols
`to generate n-bit output symbols.) The term Y, is the channel
`output (symbol) at time t.
`The MAP decoding algorithm actually first finds the prob—
`abilities:
`
`10
`
`15
`
`20
`
`1.(m)=P{SFm;Y‘r};
`
`25
`
`(1)
`
`that is, the joint probability that the encoder state at time t,
`S, is m and the set of channel outputs YL,={y,, .
`.
`. , YL} is
`received These are the desired probabilities multiplied by a
`constant (P{Y",}. the probability of receiving the set of
`channel outputs {y,. .
`.
`.
`, yL}).
`Now define the elements of a matrix 1", by
`
`I‘,(i.;)=P{1-tane j ar time t; y/staw i at time t—1.}
`
`The matrix T, is calculated as a function of the channel
`transition probability R(Y,. X), the probability p,(m/m') that
`the encoder makes a transition from state m' to m at time t,
`and the probability q,(X/m',m) that the encoder’s output
`symbol is X given that the previous encoder state is m' and
`the present encoder state is In. In particular. each element of
`F, is calculated by summing over all possible encoder
`outputs X as follows:
`
`(2)
`"((M'J'l) = Expimlm'MKle'mlflYsX)
`The MAP decoder calculates L of these matrices. one for
`each trellis stage. They are formed from the received Chan-
`nel output symbols and the nature of the trellis branches for
`a given code.
`Next define the M joint probability elements of a row
`vector (1, by
`
`30
`
`35
`
`45
`
`50
`
`(1,0)=P{rtate j at time t; y], .
`
`.
`
`.
`
`, y,}
`
`(3)
`
`55
`
`and the M conditional probability elements of a column
`vector [3, by
`
`B.(D=P{y»n -
`
`~
`
`. , yl/mvzj at time I}
`
`(4)
`
`,(M—l) where M is the number of encoder
`.
`.
`for j=0.1. .
`states. (Note that matrices and vectors are denoted herein by
`using boldface type.)
`The steps of the MAP decoding algorithm are as follows:
`(i) Calculate 0L,.
`.
`.
`.
`, or,_ by the forward recursion:
`
`on,=u.,_l1",, 1:1,. .
`
`. , L
`
`(5)
`
`60
`
`65
`
`(6)
`
`(7)
`
`(iii) Calculate the elements of 1., by:
`
`A,(z)=u,(i) [3,(1'), all 1‘, 2:1, .
`
`.
`
`. ,
`
`L.
`
`(iv) Find related quantities as needed. For example, let N,
`be the set of states S,={Sl,, 8%.
`.,S”,} such that the
`j“element of St, S’, is equal to zero. For a conventional
`non—recursive trellis code. Sj,=d’,, the j‘h data bit at time
`t. Therefore, the decoder’s soft—decision output is
`
`pp!) = omL} = -;l— 2 Mm)
`{YIL} SM?
`
`Where
`
`P{Y2L} = 2 MO”)
`m
`
`and m is the index that corresponds to a state S,
`The decoder’s hard-decision or decoded bit output is
`obtained by applying P{ d’,=0/YL} to the following decision
`rule:
`
`d}:o
`>
`P{d;=mm <
`87:1
`
`I
`2 ;
`
`That is if P{d’,=O/YL}>1/2 the di,=0; if P{d’,=0/YL}<‘/2,
`then d’}=1; otherwise. arbitrarily assign di the value 0 or 1.
`As another example of a related quantity for step (iv)
`hereinabove, the matrix of probabilities 0', comprises ele-
`ments defined as follows:
`
`o,(i,j)=P{S,_,=i; Sr'; HLI}U‘t—1(inr(iej)fir0)
`
`These probabilities are useful when itis desired to determine
`the a posteriori probability of the encoder output bits. These
`probabilities are also useful in the decoding of recursive
`convolutional codes.
`In the stande application of the MAP decoding
`algorithm, the forward recursion is initialized by the vector
`OLO=(1,0, .
`.
`. O), and the backward recursion is initialized by
`.
`BL=(1,0,
`.
`. 0)T. These initial conditions are based on
`assumptions that the encoder’s initial state So =0 and its
`ending state SL=0.
`One embodiment of the circular MAP decoder determines
`the initial state probability distribution by solving an eigen-
`value problem as follows. Let ot” [3,, 1", and k, be as before,
`but take the initial (to and [3L as follows:
`Set [3L to the column vector (111 .
`.
`. 1)T.
`Let oto be an unknown (vector) variable.
`Then,
`(i) Calculate F, for t=1, 2, . . . L according to equation (2).
`(ii) Find the largest eigenvalue of the matrix product I"1 1‘2
`.11. Normalize the corresponding eigenvector so
`that its components sum to unity. This vector is the
`solution for 010. The eigenvalue'IS P{YL1}.
`(iii) Form the succeeding or, by the forward recursion set
`forth in equation (5).
`(iv) Starting from BL, initialized as above. form the [3, by
`the backward recursion set forth in equation (6).
`
`

`

`5,734,962
`
`9
`
`(v) Form the A, as in (7), as well as other desired variables,
`such as, for example, the soft-decision output P{di,=0/
`YLl} or the matrix of probabilities 0,, described here-
`inabove.
`
`The unknown variable (to satisfies the matrix equation
`
`_ (10HF2...FL
`PinL}
`
`a"
`
`Based on the fact that this formula expresses a relationship
`among probabilities, the product of 1", matrices on the right
`has largest eigenvalue equal to P{YL,}, and that the corre-
`sponding eigenvector must be a probability vector.
`With the initial pL=(111 .
`.
`. 1)T, equation (6) gives [3“.
`Thus, repeated applications of this backward recursion give
`all the [3,. Once (10 is known and [BL is set, all computations
`in the circular MAP decoder follow the conventional MAP
`decoding algorithm
`An alternative embodiment of the circular MAP decoder
`determines the state probability distributions by a recursion
`method. In particular, in one embodiment (the dynamic
`convergence method), the recursion continues until decoder
`convergence is detected. In this recursion (or dynamic
`convergence) method, steps (ii) and (iii) of the eigenvector
`method described hereinabove are replaced as follows:
`(ii.a) Starting with an initial oto equal to (NM, .
`.
`. , 1/M),
`’ where M is the number of states in the trellis, calculate
`the forward recursion L times. Normalize the results so
`that the elements of each new 0L, sum to unity. Retain
`all L or, vectors.
`(iib) Let 010 equal (XL from the previous step and, starting
`at t=1, calculate the first me 0t, probability vectors
`again.
`That is, calculate
`
`M—I
`
`mt!!!) = :0 (Xv—(137$!!!)
`
`. . , Lwfi where me,"
`for m=0, 1, .. . , M—1 and t=1,2, .
`is a suitable minimum number of trellis stages.
`Normalize as before. Retain only the most recent set of
`L cc’ 5 found by the recursion in steps (ii.a) and (ii.b) and
`the
`
`M
`
`found previously in step (ii.a).
`(ii.c) Compare
`
`chain
`
`5
`
`10
`
`15
`
`20
`
`25
`
`30
`
`35
`
`45
`
`50
`
`from step (ii.b) to the previously found set from step
`(ii.a). If the M corresponding elements of the new and
`old
`
`55
`
`(xi-wink:
`
`are within a tolerance range, proceed to step (iv) set
`forth hereinabove. Otherwise, continue to step (ii.d).
`(ii.d) Let t=t+1 and calculate ot,=ot1_ll",, Normalize as
`before. Retain only the most recent set of L ot’s
`calculated and the ot, found previously in step (ii.a).
`(ii.e) Compare the new en’s to the previously found set. If
`the M new and old ct,’s are within a tolerance range,
`proceed to step (iv). Otherwise, continue with step
`(ii.d) if the two most recent vectors do not agree to
`
`65
`
`10
`within the tolerance range and if the number of recur—
`sions does not exceed a specified maximum (typically
`2L); proceeding to step (iv) otherwise.
`This method then continues with steps (iv) and (V) given
`hereinabove with respect to the eigenvector method to
`produce the soft—decision outputs and dec