Serial concatenation of block and
`convolutional codes
`
`S. Benedetto and G. Montorsi
`
`Indexing terms: Convolutionul 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 suboptiinuni decoding
`algorithms. The authors propose an alternative scheme consisting
`in the serial concatenation of block 01- convolutional codes and
`evaluate its average performance in terms of bit error probability.
`
`Introduction: Since their appearance in [ L], ‘turbo codes’ have been
`the object of great interest, and consequently of wide investiga-
`tion, in the coding community.
`In two previous Letters [2, 31 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 coricatcnation, 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 concatenate83 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. In 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.
`
`PCBC ( k , d
`
`I - _ _ _ _ _ _ - - - _ _ _ _ _ _ _ _ - _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ 1
`
`i outer code
`
`inner code
`
`(k, N)
`
`interleaver
`length=N
`
`(N,n)
`
`Serially 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 (k, N) code and the inner (N, n) code,
`linked by an interleaver of length N. The overall SCBC is then a
`(IC, n) code.
`As in [2, 31, a crucial step in the aniilysis 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 1 into all distinct (y) permutations of it with equal proba-
`bility l/(y). Use of the uniform 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
`
`w , h
`where A,<,,,c‘ is the number of codewords of the SCBC with weight
`h 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. I t is related to the IOWEF by
`
`Knowledge of the CWEF permits us to obtain an upper bound
`to the bit error probability of the SCBC in the form [3]
`IO
`
`887
`
`Apple 1107
`
`SNR, AWGN, d B
`17211sj
`Fig. 5 Improvement of response of PPM (+) and IPPM(0) in A WGN
`with a BDFE equaliser in the receiver
`
`Measures: The results of the previous Figures have been obtained
`on an emittingkeceiving 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 on an FPGA ALTERA
`EPM 5064 JC-1. 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 Hamamatsu C5331 APD.
`The decissor is a block maximum likelihood one.
`
`ConclusionA: 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.
`
`1 December 1995
`
`0 IEE 1996
`Electronics Letters Online No: 19960575
`R. Perez-JimCnez and V.M. Meliin (DSC, ETSI Telecomnnicacidn,
`Universidad de Las Palmas de Gran Canaria, Campus Universidad de
`TaJra, 35017 Las Palmas de Gran Canaria, Spain)
`M.J. Betancor (DET, ETSI Telecomunicaci6n, Universidad de Las
`Palmus de Gran Canaria, Campus Universidad de Tafira, 35017 Las
`Palmas de Gran Canaria, Spain
`
`References
`
`Draft IEEE P802.11. November 1995
`YEH, K : ‘IRDA’s next hurdle, total interoperatibility’, Electron.
`Des., 1995, 43,
`PEREZ-JIMENEZ. R., MELIAN, v.M., and BETANCOR, M.J.: ‘Analysis of
`multipath impulse response of diffuse and quasi-diffuse optical
`links for IR-WLAN’. Proc. INFOCOM’95, Boston, MA, USA,
`April 1995, pp. 7d.3.1-7d.3.7
`FEHER, K.: ‘Filter’. US patent 4339724, 1982
`P~REZ-JIMANEZ, R.: ‘On the study of the propagation on indoor
`wireless optical local area networks’. Doctoral Thesis, ETSIT-
`ULPGC, 1995
`CANNONE, G., MAJUMDER, s.P., GANGOPADHYAY, R., and PRATI, G.:
`‘Performance of coiivolutionally coded optical M-PPM systems
`with imperfect slot synchronization’, ZEEE Trans. Conzmun., 1991,
`39, (IO), pp. 1433-1437
`BARRY, J.R.: ‘Sequence detection and equalization for pulse position
`modukdtion’. Proc. ICC-SUPERCOM 94, New Orleans, USA,
`1994, pp. 1561-1565
`ELECTRONICS LETTERS 9th May 1996 Vol. 32 No.
`
`

`
`p b ( e ) 5
`
`k w
`k, ~i‘s(W.H)I~=e-R,E~,/.~rr
`lu=l
`where R, = k/n is the code rate and Eb/No is the signalhoke ratio
`per bit.
`The problem thus consists in the evaluation of the CWEF of the
`SCBC from the knowledge of the CWEFs of the two CCs, which
`we call AC1(w, L) and AC’(l, H). To do this, we exploit the proper-
`ties o f the uniform interleaver, which transforms a codeword of
`weight I at the output of the first encoder into all its distinct (>I
`C, of weight I generates (r) codewords of the inner code C, so that
`permutations. As a consequence, each codeword of the outer code
`the number A,,,,,C5 of codewords of the SCBC of weight 17 associ-
`ated with an input word of weight w is given by
`
`From eqn. 4 we easily derive the expressions of the IOWEF and
`CWEF of the SCBC:
`
`where AC’ (W, I) is the conditional weight distribution of the input
`word that generates codewords of the outer code of weight 1.
`Eqns. 5 and 6 can be generalised easily to the case of an inter-
`leaver of length mN, that is an integer multiple o f the length of the
`outer codewords [2] and to the case of more than two concate-
`nated codes.
`
`10’
`1 o2
`1 O3 -
`-4
`:lo
`QI
`a
`-5
`10
`1 o6
`-7
`10
`I
`0
`
`~~
`
`Fig. 2 Perfbrmunce of serially concatenuted block codes n.ir11 clifererit
`interleaver lengths
`no interleaver
`I?? = 1
`- - - -
`m = 2
`. . . . . . . .
`
`nz = 4
`rn = 8
`rii = 16
`
`. - . - . -
`
`Sei za11j concatenated convolutional codes. The structure of a seri-
`ally concatenated convolutional code (SCCC) is shown in Fig 3
`It refers to the case of two convolutional CCs of rate 112 and 213
`joined by an interleaver of length N generating a rate 113 SCCC.
`The exact analysis of this scheme requires, as illustrated in [3], the
`use of a hypertrellis having as states pairs o f atates 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
`bi anch of the hypei trellis joining the all-zero hyperstates
`
`1 o2
`1 e4
`1 o6
`-a -
`; 10
`an1p
`
`-12
`10
`18
`1 ti6
`
`0 1
`
`2
`
` 3
`
`5
`4
`EblNO
`Fig. 4 Per for nmnce of rei itillj~ and parallel tontutenated convolutional
`roties
`
`6 7
`
`8
`
`9
`
`10
`
`As an example, consider a rate 112 SCCC formed by an outer
`rate 1!2 4-state convolutional code and an inner 4-state rate 213
`convolutional 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 112 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
`inore than I dB. Moreover, the coding gain tends to increase more
`sensiblq- for the SCCC with the interleaving length. The dotted
`part of the curves reflects the uncertainty due to the limited
`number of terms considered in the computation of the union
`bound.
`
`IEE 1996
`Electronics Letters Online No: 19960621
`S. Benedetto and G. Montorsi (Dipartiinento di Elettronica, Politecnico
`rii Toi.iiio, Curso Ducti degli Abiuzzi 24, 10129 Toiino, Italy)
`
`9 February 1996
`
`References
`
`BERROU. c.. GLAVIEUX. A , and THITIMAJSHIMA, P.: ‘Near Shannon
`limit error-correcting coding and decoding: Turbo-codes’. Proc.
`ICC’93. Geneve, Switzerland, May 1993, vol. 2, pp. 1064-1070
`BENEDETTO. s , and MONTORSI, G.: ‘Average Performance of parallel
`concatenated block codes’, Electron. Lett., 1995, 31, (3), pp. 156-
`158,
`BENEDETTO, s., and MONTORSI. G.: ‘Performance evaluation of turbo
`codes’, Election. Lett., 1995, 31, (3), pp. 163-165
`
`1
`
`2
`
` 3
`
`4
`
`5
`
`6 7
`
`8
`
`1
`9 10
`
`Ackiion.I~cigii?ent. This work was supported by NATO under
`Research Grant C R G 951208.
`
`-
`
`~~
`
`IengthzN
`
`-+
`
`-+ InterLeaver --+convolutional 7
`; convolutional
`encoder, *
`:
`rate z 213
`rate = 1/2
`
`-
`
`-
`
`888
`
`ELECTRONICS LETTERS 9th May 1996 Vol. 32 No. IO