"Serial concatenation of block and
`convolutional codes
`
`S. Benedetto and G. Montorsi
`
`Indexing terms: Convolutional codes, Block codes
`
`Parallel concatenated coding schemes employing convolutional
`codes as constituent codes linked by an interleaver have been
`proposed in the literature as ‘turbo codes’. They yield very good
`performance in connection with simple suboptimum decoding
`algorithms. The authors propose an alternative scheme consisting
`in the serial concatenation of block or convolutional codes and
`evaluate its average perforiiiancc in terms of bit error probability.
`
`Intror/ur'fi0n.' Since their appearance in [l], ‘turbo codes’ have been
`the object ol‘ great interest, and consequently of wide investiga-
`tion, in the coding community.
`In two previous Letters [2, 3] we have shown how to evaluate
`the performance of parallel concatenated coding schemes using as
`constituent codes both block and convolutional codes. Here, we
`analyse an alternative to the parallel concatenation, which consists
`in the serial concatenation of two constituent codes (CCs) sepa-
`rated by an interleaver of length N. We call the obtained concate-
`nated codes SCBC (serial concatenated block codes) or SCCC
`(serial concatenated convolutional codes) according to the nature
`of the CCs. We derive an upper bound to the maximum likelihood
`bit error probability of SCBC and SCCC codes and show with
`examples that the new scheme outperforms turbo codes. 111 a com-
`panion letter, still in preparation, we will deal with the algorithms
`for iterative decoding.
`For simplicity of the exposition, we will present the methodol-
`ogy in connection with SCBC, and then extend it
`to the more
`complicated case of SCCC.
`
`
`
`\\
`
`,
`
`.
`
`3
`
`9
`
`l
`noBDFE
`
`n
`
`..
`
`
`
`4
`
`A
`
`e
`
`—*
`
`L
`
`*
`
`\
`
`il
`
`*
`
`0
`
`10
`
`J.
`10
`
`_
`
`,
`
`_5
`trioLLJ
`[0
`
`J2
`10
`
`l
`
`5.6
`10
`
`-1.
`
`o
`
`8
`4
`1713
`SNR,AWGN,dB
`Fig. 5 Improvement of response of PPAI (+) and IPPM(O) in AWGN
`with a BDFE equrzliser in the receiver
`
`12
`
`16
`
`Jvleasuress The results of the previous Figures have been obtained
`on an emitting/receiving 4-IPPM 2Mbit/s circuit prototype. A
`standard PPM codifier is added to a pulse conformation block
`that takes eight samples stored in a look—up table to give the form
`to the pulse. It has been implemented or1 an FPGA ALTERA
`EPM 5064 JC—l. The D/A is a simple and inexpensive DAC08. As
`the optical emitter we use a Siemens SFH 477 IRED with an ana-
`logue driver. As the receiver we used a Hamarnatsu C5331 APD.
`Tl1e decissor is a block maximum likelihood One.
`
`Conclusions: An alternative to the classic PPM signal has been
`outlined. IPPM requires a bandwidth that is 30% of the basic
`PPM bandwidth. IPPM improves the response of PPM against jit-
`ter. The global performances of the system against AWGN and
`low frequency interference are similar to PPM and can also be
`improved, introducing a BDFE equaliser in the receiver.
`
`© IEE 1996
`Electronics’ Letters Online No: 19960575
`
`1 December 1995
`
`Fig.
`
`I Scrially ralicatenated b/rick code
`
`R. Perez—Jimenez and V.M. Melian (DSC, ETSI T8[€C0mZlI'liCaCidH,
`Universir/rid (19 Las Palmas de Gran Czmaria, Campus Uiziversidad de
`Tnflm, 35017 Las Pu/mas ale Gum Cclnariu, Spain)
`
`(DET. ETSI Tclecomunicacién. Universidad de Las
`M.J. Betancor
`Palmas de Gran Canaria, Campus Uni‘ver.vidad do Tafira, 350/ 7 Las
`Pulrnrzv dc Gran Canaria, Spain
`
`References
`
`3
`
`4
`
`l Draft IEEE P802.ll, November 1995
`2 YEH,K.I
`‘lRDA‘s next hurdle,
`total
`interoperatibility’, Electron.
`Des, 1995, 43,
`PEREZ-JIMENEZ, 11., MELIAN,V.M., and BETANCOR, ,\r.1.: ‘Analysis of
`multipath impulse response of diffuse and quasi—diffusc optical
`links for IR—WLAl\", Proc.
`lNFOCOM'95, Boston, MA, USA,
`April l995, pp. 7d.3.l~7d.3.7
`FE]-ll:‘R,K.I ‘Filter’. US patent 4339724, 1982
`PFTRFZ-JIMFNF.7.,R.I
`‘On the study of the propagation on indoor
`wireless optical local area networks‘. Doctoral Thesis, ETSIT-
`ULPGC. 1995
`6 CANNONE,G,, MAJUMDER, s.r>.. GANGOPADHYAY, R.. and PRATI, G.1
`‘Pcrfiirinancc of cnnvoliltionnlly coded optical M-T’T’M systems
`with imperfect slot synchronization‘, IEEE Trans. Cammnn, 1991,
`39, (10), pp. 14334437
`BARRY, J.R.: ‘Sequence detection and equalization for pulse position
`modulation’. Proc.
`ICOSUPERCOM 94, New Orleans, USA,
`1994. pp. l56l—l565
`
`7
`
`Seria/ly concatenated block codes: The scheme of two serially con-
`catenated block codes is shown in Fig. 1. It is composed of two
`cascaded CCS,
`the outer (/c, N) code and the inner (N, n) code,
`linked by an interleaver of length N. The overall SCBC is then a
`(k, n) code.
`As in [2, 3], a crucial step in the analysis consists in replacing
`the actual interleaver that performs a permutation of the N input
`bits with an abstract
`interleaver called a uniform interleaver,
`defined as a probabilistic device that maps a given input word of
`weight I into all distinct (X) permutations of it with equal proba-
`bility l/(}“'). Use of the unil'0rn1 interleaver leads to a much easier
`computation of the average performance of SCBC, intended as the
`expectation over the ensemble of all interleavers of a given length
`of the performance of any SCBC with the same CCS.
`Let us define the input—output weight enumerating function
`(IOWEF) of the SCBC as
`
`A0“ ( W. H) : 2 A15; W
`w,h
`
`(1)
`
`where A,,,,,,C5 is the number of codewords of the SCBC with weight
`It associated to an input word of weight w.
`We also define the conditional weight enumerating function
`(CWEF) AC-*'(w. H) of the SCBC as the weight distribution of the
`codewords of the SCBC conditioned to a given weight w of the
`input word. It is related to the IOWEF by
`
`AC5 (w, H) :
`
`2‘
`L awacst (W, Z )%_;
`(ll
`W=D
`wt
`aww
`Knowledge of the CWEF permits us to obtain an upper bound
`to the bit error probability of the SCBC in the form [3]
`
`ELECTRONICS LETTERS
`
`9th May 1996 Vol. 32 No. 10
`
`887
`
`Apple 1007
`Apple 1007
`
`

`
`Serially concatenated convoluzional c0ci’es.' The structure of a seri-
`ally concatenated convolutional code (SCCC) is shown in Fig. 3.
`lt refers to the case of two convolutional C/Cs of rate l/2 and 2/3
`joined by an interleaver of length N generating a rate 1/ 3 SCCC.
`The exact analysis of this scheme requires, as illustrated in [3], the
`use of a hypertrellis having as states pairs of states of the outer
`and inner code. A much simpler approximation can be used, how-
`ever, when the length of the interleaver is much greater than the
`constraint
`length of the CCs:
`it consists in retaining only the
`branch 0 the hypertrellis joining the all-zero hyperstates.
`
`
`
`Fig. 4 P€)_'f0l‘I7Y((f1CC of serikzlly and parallel cancatemztcd Canvalutzfonal
`codes
`
`As an example, consider a rate l/2 SCCC formed by an outer
`rate l/2 4—state convolutional code and an inner 4—sta‘te rate 2/3
`convolntional code. joined by a uniform interleaver of length N =
`100 and 500 Using the previously outlined analysis, we have
`obtained the bit error probability bound shown in Fig. 4, where
`we have also reported the performance of a turbo code with the
`same overall rate of 1/3 obtained through the concatenation of
`two equal 4-state CCs of rate 1/2 and an interleaver of the same
`length as for the SCCC. A comparison of the two curves leads to
`the conclusion that
`the SCCC outperforms the turbo code by
`more than ldB. Moreover, the coding gain tends to increase more
`sensibly for the SCCC with the interleaving length. The dotted
`part of the curves rellects the uncertainty due to the limited
`number of terms considered in the Computation of the union
`bound.
`
`Acknon-leclgmenz.‘ This work was supported by NATO under
`Research Grant CRG 951208.
`
`IEE 1996
`Elz>(rrrmir‘s I.£ttr>r.r Ozilim? No‘ 1996062]
`5. Benedetto and G, Montorsi (D[parz[ment0 all Elellrunica, Politeuzica
`(ll Tm‘1'I70, Curtrn DJ,/m(1'r-‘g/I‘ /ibruzzi 24, /0129 Torino, Italy)
`
`9 February 1996
`
`References
`
`l
`
`ix)
`
`t,;
`
`BF.RROU.(‘., GtAv1Enx.A, and THITIMAJS]-lIMA,P.: ‘Near Shannon
`limit error—correeting coding and decoding: Turbo—codes’. Proc.
`ICC93, Gcncye, Switzerland, May 1993, Vol. 2, pp. 10644070
`BENEDETTO. s, and MONTORSL 0: ‘Average performance of parallel
`concatenated block codes’, Electron. Lezt., 1995, 31, (3), pp.
`]56—
`15s.
`BnNr.r>F,rro, s., and MONTORSL G‘. ‘Performance evaluation of turbo
`codes’, Electron. Left, I995, 31, (3), pp, 163-165
`
`/0
`
`(3)
`ate) g 2 4£l(iSl:'lLl.H)|JL1:e_R(,E,)/'3'[‘
`1.’)
`=1
`where R‘. : [cm is the code rate and Eb/NC, is the signal/noise ratio
`per bit.
`The problem thus consists in the evaluation of the CWEI-' of the
`SCBC from the knowledge of the CWEFs of the two CCS, which
`we call Afl(w.L) and AC3(l,1I). To do this, we exploit the proper-
`ties Of the uniform interleaver, which transforms a codeword of
`weight I at the output of the first encoder into all its distinct (-,‘“)
`permutations. As a consequence, each codeword of the outer code
`C, of weight [generates (V) codewords of the inner code C3 so that
`the number i4,,.,,C“ of codewords of the SCBC of weight Ii associ-
`ated with an input word of weight w is given by
`N
`C‘
`as
`A ‘‘
`>< A r
`
`433». : Z
`(1)
`1:1
`From eqn. 4 we easily derive the expressions of the IOWEF and
`CWEF of the SCBC:
`
`,
`44)
`
`.4“ (W, H) =
`
`/‘T 5’: (W1) X A02 (1, Q
`1:
`\
`I
`
`(5)
`
`(6)
`
`where AC‘ (W, l) is the conditional weight distribution of the input
`word that generates codewords of the outer code of weight 2.
`Eqns. 5 and 6 can be generalised easily to the case of an inter
`leaver of length mN, that is an integer multiple of the length of the
`outer codewords [2] and to the case of more than two concate-
`nated codes.
`
`
`
`EblNO
`
`—:~'
`
`Fig. 2 Per/brmame (g,/.s'e1‘iril[y t'om,alermled Z7lur‘k wales wit/1 tliffferml
`Iizterlemzer lengths
`—r no interlcaver —»— m : 4
`————I7'1—l
`—-— m—8
`m=2
`——'—A— m=l6
`
`As an example, consider the parity check code (4. 3) concate~
`nated through an interleaver of length 4m to a Hannning code (7.
`4). From the IOVVEF AC1(l/V. L) and AC3(L,H) of the outer and
`inner code first and second we have derived the upper bounds to
`the bit error probability plotted in Fig. 2 for various values of the
`integer m. For the sake of‘ comparison, the curve relative to the
`simple concatenation of the two codes with the identity interleaver
`of length 4 is also shown. The curves show the gain obtainable
`with the interleaver. and do not exhibit the fast gain saturation of
`the parallel concatenation of block codes [2].
`
`;
`:
`
`convolutciionot
`enco er,
`rate = 1/2
`
`mterleaver ——>cc>nvolutionol
`[
`HEN
`encoder,
`"9
`rate = 2/3
`
`, ’
`-f->
`t
`.
`
`Fig. 3 Serially mmiatenated mn,volutifmm/ code
`SCCC rate — 1/3
`
`888
`
`ELECTRONICS LETTERS
`
`9th May 1996 V0/. 32 No. 10