Meng Li

, Charbel

Abdel Nour

Christophe Jego

Catherine Douillard

Christophe Jégo

Design and FPGA prototyping of a bit-interleaved coded modulation receiver for the DVB-T2 standard

INTRODUCTION

It has been shown by Zehavi [START_REF] Zehavi | 8-PSK trellis codes for a Rayleigh channel[END_REF] that the performance of coded modulation can be improved over a Rayleigh fading channel by bit-wise interleaving at the Forward Error Correcting (FEC) encoder output, and by using an appropriate soft-decision metric at the FEC decoder input. This principle, called Bit-Interleaved Coded Modulation (BICM), currently represents the reference in coded modulations over fading channels. The SSD principle introduced in [START_REF] Giraud | Algebraic tools to build modulation schemes for fading channels[END_REF][START_REF] Boutros | Signal space diversity: A powerand bandwidth-efficient diversity technique for the Rayleigh fading channel[END_REF] improves the diversity order of BICM schemes over fading channels. It is divided into two steps. The first step consists of rotating the constellation in signal space following a particular angle value. The second step applies an interleaving of one of the In-phase (I) or Quadrature (Q) components of the signal with respect to the other. When concatenated with FEC codes, modulations with SSD show an improvement in performance for high coding rates [START_REF] Nour | Improving BICM performance of QAM constellations for broadcasting applications[END_REF] over fading channels. In the presence of erasure events, BICM with SSD achieves higher spectral efficiencies beyond the redundancy ratio of the outer FEC [START_REF] Nour | Improving BICM performance of QAM constellations for broadcasting applications[END_REF]. In addition, improvement in performance by several dBs over severe channel conditions has been observed.

The BICM with Iterative Demodulation or Demapping (BICM-ID) proposed in [START_REF] Li | Bit-interleaved coded modulation with iterative decoding[END_REF] is based on an iterative receiver with additional soft feedback from the Soft-Input Soft-Output (SISO) decoder to the constellation demapper. In [START_REF] Abramovici | On turbo encoded BICM[END_REF], the convolutional code classically used in BICM-ID schemes was replaced by a turbo code. BICM-ID with an LDPC code was studied for different DVB-T2 transmission scenarios in [START_REF] Nour | Improving BICM performance of QAM constellations for broadcasting applications[END_REF]. The authors show that an iterative demapping associated with SSD provides additional error correction that can exceed 1.0 dB over some channel types. Thanks to theses advantages, BICM-ID has been pointed out in the implementation guidelines of the DVB-T2 standard [START_REF] Dvb-T2 | Implementation guidelines for a second generation digital terrestrial television broadcasting system (DVB-T2)[END_REF] as one of the important means for improving performance at the receiver side. Best DVB-T2 error rate performance results are obtained when iterative demodulation is applied.

However, the application of BICM-ID with SSD has an important impact on the design of the rotated QAM demapper and the LDPC decoder. When Gray mapping is used, applying a rotation to the signal constellation breaks the independence between the in-phase and quadrature components of the QAM. Consequently, the Maximum Likelihood (ML) QAM detector cannot apply two independent Pulse Amplitude Modulation (PAM) detectors anymore. Instead, both I and Q signal components are needed for the computation of the demapper metrics. The design of high throughput, low complexity, low latency architectures for a BICM with SSD becomes a challenge. In [START_REF] Li | Design of Rotated QAM Mapper/Demapper for the DVB-T2 Standard[END_REF], flexible mapper and demapper architectures for DVB-T2 are presented. The decomposition of the constellation into two-dimensional sub-regions in signal space associated with additional algorithmic simplifications represents the main novelty of [START_REF] Li | Design of Rotated QAM Mapper/Demapper for the DVB-T2 Standard[END_REF]. They enable to strongly decrease the complexity of the demapper.

LDPC codes can be efficiently decoded using the Belief Propagation (BP) algorithm. This algorithm operates on the bipartite graph representation of the code by iteratively exchanging messages between the variable and check nodes along the edges of the graph. The Min-Sum (MS) algorithm, which is an alternative method, can significantly reduce the hardware complexity of the BP algorithm. Moreover, modified versions of MS algorithm such as normalized MS or offset MS using additional correction factors offer comparable decoding performance over the BP algorithm. Based on these different improvements, many LDPC decoders have been described in previous papers; a brief review can be found in [START_REF] Guilloud | Generic description and synthesis of LDPC decoder[END_REF]. The schedule defines the order of passing messages between all the nodes of the bipartite graph. Since a bipartite graph contains some cycles, the schedule directly affects the algorithm's convergence rate and hence its computational complexity. The classical schedule is flooding where decoder iteration is divided into two phases: in the first phase, all the variable nodes send messages to their neighbouring check-nodes, and in the next phase the check-nodes send messages to their neighbouring variable nodes. More efficient layered schedules have been proposed in literature [START_REF] Hocevar | A reduced complexity decoder architecture via layered decoding of LDPC codes[END_REF]. Indeed, the parity check matrix can be viewed as a horizontal or a vertical layered decoded sequentially. Decoder iteration is then split into sub-layer iterations. The layered schedules enable the decoding convergence to speed up. They can also ensure a good matching between decoding algorithms on one hand and decoder architectures on the other hand.

For a BICM-ID scheme, an efficient exchange of extrinsic information between the demapper and the decoder has to be applied. Indeed, the ID imposes a latency that can have an important impact on the whole receiver. Shuffled versions of the standard iterative decoding algorithms for both LDPC and turbo codes are presented in [START_REF] Zhang | Shuffled iterative decoding[END_REF]. The proposed schemes have about the same computational complexity as the standard versions while enjoying faster iterative process convergence. This principle can be extended to BICM-ID in order to design a low-latency receiver. It forces however a vertical layered schedule for the decoding of the LDPC codes. Vertical layered schedule for the BP algorithm is found in literature. To our knowledge, normalized MS based on vertical layered decoding was only studied in [START_REF] Cui | Efficient Decoder Design for High-Throughput LDPC Decoding[END_REF]. Moreover, the problem of memory access conflicts for layered architectures has never been addressed in the case of a normalized MS based on vertical layered decoding. As a possible solution, we extend the reordering mechanism of the DVB-T2 parity check matrix detailed in [START_REF] Marchand | Conflict Resolution by Matrix Reordering for DVB-T2 LDPC Decoders[END_REF], to a vertical layered schedule. We also solved the message updating inefficiency caused by the double diagonal sub-matrices during the decoder design.

The remainder of the paper is organized as follows. Section 2 recalls the basic principles of the BICM-ID and SSD. Section 3 details a vertical layered decoding using a normalized MS algorithm. The challenging issue of resolving memory conflicts is developed in Section 4. Finally, an implementation of the proposed LDPC decoder for a BICM receiver and its experimental setup onto an FPGA device are presented.

BICM-ID SYSTEM

The channel model used to simulate and emulate the effect of erasure events is a modified version of the classical Rayleigh fading channel. More information about this model is given in [START_REF] Li | Design of Rotated QAM Mapper/Demapper for the DVB-T2 Standard[END_REF].

BICM-ID with SSD

The SSD principle consists of introducing modifications to the mapper and demapper as shown in Fig. 1. The QAM constellation is rotated by an angle α and the component axes are interleaved [START_REF] Li | Bit-interleaved coded modulation with iterative decoding[END_REF]. The in-phase and quadrature components are therefore subject to two different fading coefficients increasing the degree of diversity of the BICM scheme. The information frame u goes through the FEC encoder to generate the codeword c . Afterwards, this sequence c is interleaved using the bit interleaver π to generate the mapper input sequence v. At time t, m consecutive bits of the interleaved sequence v are mapped to complex symbol t x . At the receiver side, the Log Likelihood Ratio (LLR) computation has to take into account the introduced modifications (cf. Fig. 1(b)). For Gray-mapped QAM constellations, the demapper calculates a two-dimensional squared Euclidean distance for the computation of the LLR ˆi t v related to the i th bit of v t . After de-interleaving, the LLRs are used as inputs to the decoder. When the received signal t y is erased, the LLR computation is updated accordingly.

The extrinsic exchange of soft information is initiated between the decoder and the demapper thanks to a soft feedback.

The LDPC code of the DVB-T2 standard

Irregular Repeat Accumulate (IRA) codes are a family of special LDPC codes which can be encoded/decoded with linear complexity while still keeping good BER performance. An IRA code is characterized by a parity check matrix composed of two sub-matrices: a sparse sub-matrix and a staircase lower triangular sub-matrix. Moreover, periodicity has been introduced in matrix design in order to reduce storage requirements. This family of LDPC codes has been adopted in the DVB-T2 standard. Unfortunately, the parity check matrices are not perfectly structured for layered decoding architectures, leading to some memory access conflicts. Moreover, an important issue in the design of LDPC decoder architectures for DVB-T2 is the fact that the standard supports multiple frame and code rate scenarios. Actually, two different frame lengths (16200 bits and 64800 bits) and a set of different code rates (1/2, 3/5, 2/3, 3/4, 4/5 and 5/6) have been adopted. In this paper, we propose a novel LDPC decoder architecture particularly suited to the BICM-ID context in order to closely approach best performance results provided in the implementation guidelines of the DVB-T2 standard.

A VERTICAL LAYERED DECODING SCHEME USING A NORMALIZED MS ALGORITHM

Vertical layered schedule

By means of the Gauss-Seidel algorithm, a vertical layered schedule for the BP algorithm updates the messages between check and bit nodes in a column by column way. In the sake of clarity, the algorithm is described as a fully serialized version, in which the messages are processed one by one. Let n llr denote the intrinsic channel reliability value of the variable node n , mn E denotes the message sent from check node m to bit node n , mn T denote the message sent from variable node n to check node m and n T denote a posteriori log-likelihood ratio of bit node n during each iteration.

Vertical layered BP algorithm 0. Initialization: 1.

(0) mn n T llr = ( ) m M n ∈ 2. (0) ( ) sgn( ) m n m M n llr α ∈ = ∏ , (0) ( ) ( ) m n m M n llr β ϕ ∈ = ∑ 3. Iterative decoding 4. max 1, 2,..., t t ∀ = // iteration 5. 1, 2,..., n N ∀ = // sub-iteration // check node processing 6. ( ) ( 1) ( 1) sgn( ) ( ( )
T T α α - = ⋅ ⋅ ( ) m M n ∈ 9. ( 1) ( ) ( ) ( )
t t m m mn mn T T β β ϕ ϕ - = - + ( ) m M n ∈ 10.
Hard decision according to sign(

( ) t n T )
The decoding algorithm consists of passing messages mn T from variable nodes to parity check nodes and messages mn E from parity check nodes to variable nodes during an iterative process. In the serial vertical layered algorithm, one iteration is split into n sub-iterations, one for every layer.

( )\ ( )\ ( ) ( ) t t m m n m n n N m n n N m n n n n n T T β ϕ ϕ - ∈ ∈ < > = + ∑ ∑ ' ' ' ' ( ) ( 1)
( )\ ( )\ sgn( ) sgn( )

t t m m n m n n N m n n N m n n n n n T T α - ∈ ∈ < > = ⋅ ∏ ∏
The vertical layered schedule is particularly suited for a hardware design in the sense that it can reduce the required number of memory accesses. mn T is used and updated only once by iteration and the m α and m β are used and updated dc times by iteration.

Normalized MS algorithm

A normalized MS vertical layered message passing algorithm has been studied to reduce hardware complexity. Following the principle of MS algorithm for horizontal layered decoding, the vertical layered MS uses λ (

P ) ( ) ( 1) 1
sgn( )

t t mn m mn m E T M α η - = ⋅ ⋅ ⋅ else ( ) ( 1) 0 sgn( ) t t mn m mn m E T M α η - = ⋅ ⋅ ⋅ // bit node processing 10. ( ) ( )
( ) t t n n m n m M n T llr E ∈ = + ∑ ( ) ( ) ( ) t t t mn n mn T T E = -
// check node update for next sub-iteration 11.

( 1) ( ) sgn( ) sgn( )

t t m m mn mn T T α α - = ⋅ ⋅ ( ) m M n ∈ 12. ' 0 ( ) (1 )
min( , )

t t m m n mk M T T - = ' ( ) \ k N m n ∈ 13. ' 1 ( ) ( 1 )

DESIGN OF AN LDPC DECODER FOR BICM

The DVB-T2 LDPC codes are architecture-aware codes. It means that a pipeline decoder can be implemented in parallel to improve the throughput. But, similarly to the horizontal layered decoder, the memory access conflict problem is the bottleneck of the design of a high throughput, low complexity vertical layered MS LDPC decoder. To our knowledge, this is the first architecture design that overcomes memory access conflicts without additional delays in the decoding process when a normalized MS vertical layered message passing algorithm is considered. Unlike a horizontal layered decoder, it is not possible to assign only one barrel shifter in the vertical layered decoder. Indeed, the information exchange between SISO-A and SISO-B processors has to deal with two different cases: LLR initialization and classical exchange.

Architecture of a vertical layered MS LDPC decoder

( ) t mn E n T ( ) t mn T ( ) t n T 0 1 0 M 1 M 0 index P = α α ( ) ( 1 )
sgn t T - ( )
( ) sgn t mn E ( ) t mn E ( )
( ) sgn t T ( ) t T ( ) ( 1 )
sgn t T - 0 1 , M M

Memory access conflict resolution

A pipeline process is generally applied in order to increase the throughput. The main bottleneck is the memory access conflicts for the check node memory bank in the case of a vertical layered MS LDPC decoder. Fig. 4 shows the scheduling of one sub-iteration for three column layers with a bit node degree of three, where MP means the check node memory bank. In this case, six periods are necessary for updating the check node memory bank. cad is read out more than once before the update of 0,0 MP , then there is a memory access conflict. The condition that leads to a conflict-free memory access is:

0,0 MP 1,0 MP 2,0 MP 0,1 MP 1,1 MP 2,1 MP 0,2 MP 0,3 MP 1,3 MP 0,0 E 1,0 E 2,0 E 0,1 E 1,1 E 2,1 E 0,2 E 1,2 E 0,0 T 1,0 T 2,0 T 0,1 T 0,0 MP 1,0 MP 2,0 MP ( ) old SISOB ij E ij T ( ) new SISOB = 3+3=6 delay dv ε = +
{ } { } ( ) clk delay of i i j j cad dv cad ε ∩ + =∅
To respect this constraint, we propose a design process without additional idle time. The first step is applied to the set of { } i j cad for each column j. Permutations are done between the addresses of all the check node processors connected to one bit node processor. After splitting the submatrix like in [START_REF] Marchand | Conflict Resolution by Matrix Reordering for DVB-T2 LDPC Decoders[END_REF], this first step of the construction process enables to overcome 90 percent of the memory access conflicts. For the unsolved cases, a second step is applied to

the set of { } { } { } { } 0 1 1 , , , i i i n cad cad cad - ⋅⋅⋅
for all the columns.

Permutations done during this second step introduce some additional hardware control to manage the input/output accesses of bit node processors. However, the corresponding hardware cost is very low thanks to the reduced number of required permutations.

Conflicts due the parity check matrix structure

Parity check matrices for DVB-T2 LDPC codes are structured with shifted identify sub-matrices. Unfortunately, some sub-matrices contain two diagonals. It means that groups of variable nodes are connected twice to groups of check nodes. So, Double Diagonal Sub-Matrices (DDSM) introduce some memory access and update conflicts that have to be resolved during the decoder design. For example, if the column layer 0 of Fig. 4 has a DDSM, then two addresses 0 0 cad and 1 0 cad have to be processed at the same time. In this case, it is very difficult to avoid the conflict by a reordering mechanism, so the read data

BICM RECEIVER DESIGN AND PROTOTYPING

In order to validate the BICM receiver, BER performance measures have to be carried out. For this reason, we have integrated a channel emulator from a classical Rayleigh fading channel adjusted to hardware implementation. The channel emulator is obtained from an AWGN generator of multiples variables. The hardware emulator is achieved using the Wallace method. Moreover, erasure event modeling was added to the channel emulator as explained in section 2.1. This module needs 4,907 slice Flip-Flops and 6321 slice LUTs. In addition, 59 DSP resources are necessary for multiplications and 13 BlockRAMs are also assigned.

The experimental setup is a development board from Dinigroup that contains 6 Xilinx Virtex5 LX330 devices. Fig. 6 shows the different components of the experimental setup implemented onto only one of the FPGAs. A Pseudo Random Generator (PRG) sends out pseudo random data streams at each clock period f 0 . This module is composed of flip-flops and XOR gates. An LDPC encoder processes the data streams. The codeword bits are then re-ordered thanks to the DVB-T2 interleaver. The last task of the transmitter is the mapping. The channel emulator previously describe generates emulator previously described generates Rayleigh fading samples with or without erasures and adds them to the data streams. The BICM receiver is made up of a demapper, a deinterleaver and an LDPC decoder. In the experimental setup, we have as well integrated the rotated demapper previously described in [START_REF] Li | Design of Rotated QAM Mapper/Demapper for the DVB-T2 Standard[END_REF]. The proposed vertical layered MS LDPC decoder was synthesized and implemented onto the FPGA. Computational resources of the decoder take up 12,178 slice Flip-Flops and 37,161 slice LUTs. It means that the occupation rates are about 5% and 17% of a Xilinx XC5VLX330 FPGA for slice registers and slice LUTs, respectively. In addition, memory resources for the decoder take up 84 BlockRAMs of 18kbits or 36kbits. The maximum frequency estimated after logic synthesis is 122MHz, this result in a throughput of 174 Mbps, for R=3/4 @ 15 iterations. A comparison of simulated performance and measured performance in terms of BER of the designed BICM for a QPSK constellation, a code rate R=3/4 and 64,800 bit frames, is presented in Fig. 7. The prototype shows quasi-identical performance when compared to fixed-point simulation for a maximum number of 25 decoding iterations.

CONCLUSION

BICM-ID shows best performance in the implementation guidelines of the DVB-T2 standard. In this paper, a normalized MS decoder architecture based on a vertical layered schedule is presented. It enables an efficient exchange data process between the demapper and the decoder in the ID context. In addition, a prototype based on a FPGA device has been done to validate the performance of the proposed LDPC decoder for DVB-T2.

Fig. 1 :

 1 Fig. 1: the BICM-ID with SSD structure (a) transmitter and (b) receiver

  First, the messages mn T and values m α and m β are initialized with the intrinsic channel reliabilities n llr . Each sub-iteration is composed of three steps: check node processing, bit node processing and m α , m β value update. The check node processing is based on the property of 1 the a posteriori log-likelihood ratio ( ) t n T for bit node n is achieved by adding all the ( ) t mn E to n llr . The messages ( ) t mn T are computed from ( ) t n T . The m α , m β values are updated according to the messages ( ) t mn T . Finally, the hard decision is taken from the sign of ( ) t n T . One of the main advantages of the vertical layered schedule is faster decoding convergence. By comparison with a flooding schedule, less iterations are needed thanks to the computation of variables m

.M

  decision according to sign( ( ) Let η denote the scaling factor for the correction of the over-estimation introduced by the MS algorithm. Thus, the most complex part of normalized MS vertical layered message passing algorithm is the update of that this part is quite different from the horizontal layered schedule. Let's take the update of 0 m M at the th n sub-iteration as an example. Three cases have to be considered. 1needs a third minimum value as a candidate of the second minimum ( 3 λ = ). However, simulation results showed that only 0.05dB performance penalty is observed if λ=2. Consequently, this value has been chosen in our study. The impact of the normalized vertical layered MS algorithm for the decoding of DVB-T2 LDPC codes is illustrated in Fig. 2. Simulations were carried out for four decoding algorithms with a maximum number of 50 iterations: horizontal and vertical layered BP, floating-point and fixed-point versions of vertical layered normalized MS. For comparison, the uncoded 256-QAM is also plotted. Simulation results show that no significant BER deviation is observed between horizontal and vertical layered BP algorithms. BP algorithm outperforms normalized MS algorithm by about 0.4 dB at 10 -6 . An additional penalty of 0.3 dB is introduced for a fixed-point version of the normalized MS algorithm. Results show decoding performance close to floating-point BP algorithm.

Fig. 2 :

 2 Fig. 2: BER at the outputs of the demapper and LDPC decoder for BP and normalized MS algorithms. Code rate R = 3/4, rotated 256-QAM constellation, and 64,800-bit frames. Transmission over flat fading Rayleigh channel with 15% of erasure events.

Fig. 3

 3 Fig. 3 details the architecture of the proposed vertical layered MS LDPC decoder for the DVB-T2 standard. It consists of two main blocks: bit node processor SISO-A and check node processor SISO-B. Since the DVB-T2 standard supports two long frames, 90 SISO-A and 90 SISO-B blocks have been designed to work in parallel in our architecture. For one sub-iteration, the 0 m M , 1 m M , 0 m P , m α

Fig. 3 :

 3 Fig. 3: Architecture of the vertical layered MS LDPC decoder

Fig. 4 :

 4 Fig. 4: Scheduling of the vertical layered MS LDPC decoder

1 , 0 Fig. 5 :

 105 Fig. 5: Architecture for resolving update conflicts caused by the DDSMs

Fig. 7 :

 7 Fig. 7: Performance of BICM for fading channel without and with 5 % of erasures

  )

		E	mn	t	=	α	m	⋅	t mn T -	⋅	m ϕβ ϕ -	t mn T -
	7.	// bit node processing ( ) ( ) t n n m n m M n T llr E ∈ = + ∑	( ) t	( ) t mn T	=	( ) t n T	-	( ) t mn E
		// check node update for next sub-iteration
	8.	m		m	sgn(	( 1) t mn	( ) t ) sgn( ) mn

ACKNOWLEDGMENT

The authors would like to thank Gerald Le Mestre for his help during the experimental setup design. This work has been carried out in the framework of the SME42 project of the EUREKA's Eurostars programme.


Camille Leroux

Christophe Jego

Patrick Adde

Michel Jezequel

Deepak Gupta

A HIGHLY PARALLEL TURBO PRODUCT CODE DECODER WITHOUT INTERLEAVING RESOURCE

Keywords: Product codes, Parallel architectures, Ultra-high-speed integrated circuits

This article presents an innovative Turbo Product Code (TPC) decoder architecture without any interleaving resource. This architecture includes a full-parallel SISO decoder able to process n symbols in one clock period. Syntheses show the better efficiency of such an architecture compared with existing previous solutions. Considering a 6-iteration turbo decoder of a (32,26) 2 BCH product code, synthetized in a 90nm CMOS technology, the resulting information throughput is 2.5Gb/s with an area of 233Kgates. Finally a second architecture enhancing parallelism rate is described. The information throughput is 33.7Gb/s while an area estimation gives A =10µm 2 .

INTRODUCTION

Nowadays, high throughput telecomunication systems such as optical fiber transmission systems or passive optical networks require powerfull error correcting codes in order to increase their optical budget. Iterative decoding provides effective solutions for next generation optical systems. Recently, a (660,480) LDPC code decoder ASIC implementation was proposed. The information throughput is 2.4Gb/s while it could be enhanced to 10Gb/s with a (2048,1723) LDPC code [START_REF] Darabiha | A 3.3-gbps bit-serial block-interlaced min-sum ldpc decoder in 0.13-um cmos[END_REF]. Turbo product codes [START_REF] Pyndiah | Near optimum decoding of product codes[END_REF] also tend to be good candidates for emerging optical systems [START_REF] Mizuochi | Next generation fec for optical transmission systems[END_REF]. In [START_REF] Mizuochi | Experimental demonstration of net coding gain of 10.1 db using 12.4 gb/s block turbo code with 3-bit soft decision[END_REF], a BTC decoder is included in a 12.4Gb/s optical experimental setup. Since only a part of the transmitted data are actually coded, the information throughput of the BTC turbo decoder is 156Mb/s. The inherent parallel structure of the product code matrix confers to TPC good ability for parallel decoding. Nevertheless, enhancing parallelism rate rapidly induces the use of a prohibitive amount of memory. Some solutions were proposed in [START_REF] Cuevas | New architecture for high data rate turbo decoding of product codes[END_REF] [START_REF] Zhipei | High speed vlsi architecture design for block turbo decoder[END_REF] [START_REF] Jego | Full-parallel architecture for turbo decoding of product codes[END_REF] to efficiently use the interleaving resources (IR), reaching high parallelism rates. However, a particular scheduling of the product code matrix enables to propose a turbo decoder architecture without any interleaving resource.

After a brief introduction of the TPC coding and decoding concept in section 2, section 3 reviews previous works and proposes an innovative TPC decoder architecture without any interleaving resource. This new TPC decoder includes a new full-parallel SISO decoder architecture which is described in section 4. Section 5 gives some synthesis results and demonstrates the better efficiency of the proposed BTC decoder. Finally, a solution is proposed to enhance parallelism rate while highering the architecture efficiency. The interconnection issue is assessed and compared with an equivalent LDPC code decoder implementation.

TPC CODING AND DECODING PRINCIPLES

Product codes

The concept of product codes is a simple and efficient method to construct powerful codes with a large minimum Hamming distance d using cyclic linear block codes [START_REF] Elias | Error-free coding[END_REF]. Let us consider two systematic cyclic linear block codes C 1 having parameters (n 1 , k 1 , d 1 ) and C 2 having parameters (n 2 , k 2 , d 2 ) where n i , k i and d i (i = 1, 2) stand for code length, number of information symbols and minimum Hamming distance respectively. The product code P = C 1 × C 2 is obtained by placing (k 1 × k 2 ) information bits in a matrix of k 1 rows and k 2 columns, coding the k 1 rows using code C 2 and coding the n 2 columns using code C 1 .

Considering that C 1 and C 2 are linear codes, it is shown that all n 1 rows are codewords of C 2 exactly as all n 2 columns are codewords of C 1 by construction. Furthermore, the parameters of the resulting product code P are given by n

p = n 1 × n 2 , k p = k 1 × k 2 , and d p = d 1 × d 2 and the code rate R p is given by R p = R 1 × R 2 .
Thus, it is possible to construct powerful product codes using linear block codes. In the following sections, we will consider a squared product code, meaning that n 1 = n 2 = n. The most commonly used component codes are Bose Chaudhuri Hocquenghem (BCH) codes. These codes are an infinite class of linear cyclic block codes that have capabilities for multiple error detection and correction. Product codes were adopted in 2001 as an optional correcting code system for both the uplink and downlink of the IEEE 802.16 standard (WiMAX) [9].

Iterative decoding of product codes

TPC decoding involves successively decoding rows and columns using SISO decoders. Repeating this soft decoding during several iterations enables the decrease of the Bit Error Rate (BER). It is known as the TPC decoding process. Each decoder has to compute soft information [R ] it+1 from the channel received information [R] and the previous half-iteration computed information [R ] it .

Despite the existence of other decoding algorithms [START_REF] Forney | Generalized minimum distance decoding[END_REF], the Chase-Pyndiah algorithm is known to give the best tradeoff between performance and decoding complexity [START_REF] Adde | Performance and complexity of block turbo decoder circuits[END_REF]. The Chase-Pyndiah SISO algorithm for a t = 1 BCH code [START_REF] Chase | A class of algorithms for decoding block codes with channel measurement information[END_REF]

≤ t i ≤ T -1)
• Compute the syndrome S(t i ),

• Correct the potential error by inverting the bit position S(t i ),

• Recompute the parity considering the detection of an error and the parity of [R ] it ,

• Compute the square Euclidian distance (metric) M i between [R ] it and the considered test pattern t i .

6. Select the Decided Word (DW) among test patterns having the minimal metric (M DW ) and choose Cw competitors codewords c i (1 < i < Cw) having the second minimum metric.

7.

For each symbol of the DW,

• Compute the new reliability

F it = min 2 (M i )-min(M i ) or F it = β when no competitor exists, • Compute extrinsic information W it = F it -R it ,
• Add extrinsic information (multiplied by α it ) to the channel received word,

R it+1 = R + α it W it .
The α it coefficient allows decoding decisions to be damped during the first iterations. As detailed in [START_REF] Leroux | Towards gb/s turbo decoding of product code onto an fpga device[END_REF], decoding parameters p, T , and Cw have a notable effect on decoding performance. The number of quantization bits of the soft information q also impacts on performance.

PARALLEL DECODING OF PRODUCT CODES

Previous work

Many TPC decoder architectures were previously designed. The classical high speed approach involves the use of a pipelined structure at the iteration level. Separate decoding resources are assigned for each half-iteration. In existing architectures, the reconstruction of the matrix is necessary between each iteration: memory blocks are used between each half-iteration to store [R ] it and [R]. Each interleaving memory block is then composed of four memories of q × n 2 symbols. This solution presents several drawbacks. First, a large amount of memory is required which increases the global latency and the complexity of the design. In addition, increasing the parallelism degree of each half-iteration produces memory conflicts when several data have to be adressed at the same time.

In 2002, a new architecture was proposed [START_REF] Cuevas | New architecture for high data rate turbo decoding of product codes[END_REF] in order to increase the parallelism degree without any extra storage between half-iteration. The idea was to store several product code matrix symbols at the same address and to use elementary decoders able to process m symbols during the same clock period (denoted as m-decoders). A half-iteration structure includes m decoders each decoding m symbols in one clock period and an interleaving memory of size 4qn 2 . The resulting throughput is O(m 2 ) while the overhead factor of the decoder complexity is ∼ m 2 2 . In [START_REF] Zhipei | High speed vlsi architecture design for block turbo decoder[END_REF], authors suggested to use a barrel shifter between decoding resources and the interleaving memory (IM) in order to avoid memory conflicts. This solution enables reaching the parallelism rate P = n by rotating the to be stored data. The extra-complexity only consists in a barrel shifter with a complexity in O(n log(n)). However, the IM requirement is still prohibitive.

In [START_REF] Jego | Full-parallel architecture for turbo decoding of product codes[END_REF][13], an IM-less architecture is detailed and prototyped on an FPGA device. In this architecture, a particular scheduling of the product code matrix decoding enables the interleaving memory to be replaced by an interconnection network (omega network). The complexity of the interleaving resources is then drastically reduced and highly-parallel structure can be implemented onto low-cost targets.

Memory (1/2 iteration) Throughput IM Internal [5] O(m 2 ), m < n m max = 8 O(4qn 2 ) O(2sqnm) [6] O(n) O(4qn 2 ) +O(n log n) O(2sqn 2 ) [7][13] O(n) O(n log n) O(2sqn 2 )
Table 1. Throughput and complexity order of previous highspeed architectures

These three architectures can reach high parallelism degrees (i.e. high throughput). However, as illustrated on in table 1, the internal memory complexity remains an important issue in the design of high-throughput TPC decoders. s is the number of pipeline stages inside the SISO decoder. Moreover, in these architectures, decoding resources consist in a duplication of sequential decoders. Increasing the parallelism rate by duplicating computation resources is inefficient since the reuse of available resources is not optimized. In the next section, we propose to merge the duplicated sequential SISO decoders into one full-parallel SISO decoder.

Proposed IM-free architecture using full-parallel SISO decoder

Considering that one can design a SISO decoder able to process n symbols in parallel in one clock period, a product code matrix can be decoded without any interleaving resource as shown in figure 1. As explained in section 2, the Chase-Pyndiah algorithm includes parameters (p, T, Cw, q) which impact on both the performance and the complexity of the turbo decoding. Performing 8 iterations, the parameter set p 0 = {p = 5, T = 16, Cw = 3, q = 5} gives the best performance for a reasonnable complexity [START_REF] Adde | Performance and complexity of block turbo decoder circuits[END_REF]. However, algorithmic simulations showed that the reduced parameter set p 1 = {p = 3, T = 8, Cw = 0, q = 5} only induce a performance loss of 0.25dB at BER= 10 -6 while it becomes nul below BER= 10 -9 . Consequently, using p 1 enables the architecture to be simplified for a limited performance lost. The syndrome of the incoming vector R it can be derived as S(R it ) = H × sign(R it ) where H is the parity check matrix of the BCH code. A straightforward implementation of such a matrix multiplication is depicted on figure 4. The H matrix, the corresponding parity check equations and the syndrome S(t 0 ) = [s 2 , s 1 , s 0 ] implementation of a (7,4) BCH code are detailed. It can be noticed that some parity check equations have similar terms. For instance, the term (x 1 ⊕ x 0 ) is used in both s 1 and s 2 computation. This enables a reuse of computation resources for an even more efficient implementation. The parity of the incoming vector R it is computed with a similar structure by "xoring" (n -1) incoming bits.

Full-parallel SISO decoder architecture

Selecting the least reliable bits among the incoming vector in parallel requires a sorting network. Such structures are composed of interconnected Compare and Select operators (CS). The interconnection scheme depends on the considered sorting algorithm. Many parallel sorting algorithm are conceivable [START_REF] Akl | Parallel sorting algorithms[END_REF]. However, most of them are optimized for a complete sorting, while the Chase-Pyndiah algorithm only requires a partial sorting (i.e. extracting p minima). Consequently we devised a network optimized, in terms of area and critical path, for the partial sorting of p=3 values among n=32, as depicted on figure 5. The structure is based on shuffle networks coupled with local minima computation blocks. After the first shuffle stage, min 1 is in the lower section while the upper section can either contain min 2 or min 3 or no minimum. The same reasonning is applied recursively. After 5 shuffle stages, the minimum is determined while 5 values can still be min 2 and min 3 . A local sorting of this 5 values enables the determination of min 2 and min 3 value. This partial sorting network requires 35 CS and 29 minimum elements. The critical path consists in 9 comparisons stages.

Test pattern processing stage

The test pattern processing stage corresponds to steps (4-5) in the Chase-Pyndiah algorithm detailed in section 2. Instead of being processed sequentially, test patterns are processed in parallel. The syndrome of each test pattern is computed by adding S(t 0 ) with the position of the inverted reliable bits. The parity management block computes the parity of R it+1 considering the parity of R it and the detection of an error which is the case when S(t i ) = 0. Metrics of each test pattern is then computed by adding the contribution of each inverted bit in the current test pattern (least reliable bits, syndrome corrected bits and, the new parity bit). The minimum metric is determined in the DW selection block. The structure is a simple minimum selection tree. The multiplexer selects R it (S(t i )) in order to compute test pattern metrics.

Soft output computation stage

The last stage is a duplication of n soft output computation blocks. As shown on figure 6, this block first computes the new reliability F it of each symbol. Since, no competitor is considered, the β value is automatically assigned. The β value is based on an estimation of the competitor word metric value. It is calculated with the reliability of the corrected bit and the least reliable bits. Then, the extrinsic information is computed and damped by the coefficient α it which is devised to be a power of 2 making the multiplication a simple bit shifting. Finally, the channel information is added to generate the soft output R it+1 . Within this block, all computation are performed in sign and magnitude format. Other arithmetic format were explored but the chosen one requires less computation resources than others.

AREA VS THROUGHPUT TRADEOFF

In this section, we compare the parallel and the sequential SISO decoders in terms of throughput, complexity and ef-Fig. 6. Soft output computation stage ficiency. Then a pipelined version of the parallel SISO decoder is proposed. Logic syntheses were performed using Synopsys Design Compiler with a ST-microelectronics 90nm CMOS process. The area is transposed in logic gate count. One equivalent logic gate corresponds to the area of a 2-input NAND gate. It enables a more technology-independant measure of the complexity.

Logic synthesis results

We designed 5 versions of the (32,26) BCH parallel SISO decoder having from 1 to 5 pipeline stages. The 1-pipeline stage version is a full-combinatorial architecture with register banks only in input and output. Table 2 summarizes synthesis results of the 5 different full-parallel SISO decoder and compare them with n duplicated sequential SISO.

s is the number of pipeline stages, f max is the maximum working frequency reached during synthesis, A represents the area of the design in equivalent gate count, the parallelism rate P corresponds to the number of processed symbols per clock period. T in is the input throughput such as T in = P × f and T out is the information throughput T out = R p × P × f . Increasing throughput regardless of turbo decoder complexity is not relevant. In order to compare the throughput and complexity of SISO decoders, the efficiency of each decoder is defined as : η = Tout A .

Parallel 2 shows that the parallel SISO decoder can reach high throughput with low complexity. This clearly shows the higher efficiency of the parallel SISO decoder compared with a duplication of n sequential decoders. Actually a fully parallel structure enables a better reuse of computation and memory resources. For instance, in a parallel SISO decoder, the memory requirement for R and R it are O(2sqn) while in a sequential-based parallel decoder, it is O(2sqn 2 ).

Since the resulting throughput is limited by the slower stage, the maximum throughput of a full-iteration module is 14.8Gb/s. In this case, a full-iteration of the proposed architecture (see figure 2b) takes 236Kgates while the previous architecture (see figure 2a) takes 400Kgates.

Towards a maximal parallelism rate

Previous synthesis results showed the better efficiency of parallel architecture compared with duplicated architectures.

Alternative turbo decoding scheduling for enhanced parallelism rate Figure 5.2 proposes an alternate product code matrix parallel decoding scheme where m parallel decoders are used for column decoding while row decoding is performed by n mdecoders. A m-dec decoder can decode m symbols in one clock period and 1 < m < n [START_REF] Cuevas | New architecture for high data rate turbo decoding of product codes[END_REF]. In such an architecure, the maximum reachable parallelism rate P = n 2 can be achieved by using n full-parallel SISO decoder for column decoding and n full-parallel SISO decoder for row decoding. Considering that the TPC decoder includes 2n parallel SISO decoders (with s = 5 pipeline stages) for it decoding iterations, the turbo decoder output throughput is

T out = P × f × R p it
Placing and routing 2n parallel SISO decoders would reduce the maximum working frequency of the parallel SISO decoder. Nevertheless, using the previous equation, an information throughput T out =10Gb/s is reached when f >88MHz which is a most probably acheivable frequency Furthermore, a reasonnable working frequency of f =300MHz leads to a (32,26) 2 BCH product code turbo decoder with an information throughput T out =33.7Gb/s. The total area of such a parallel turbo decoder is A = 10µm 2 . The achieved parallelism rate (P = n 2 =1024) is similar to a full parallel n =1024 LDPC decoder. The number of interconnection among the product code turbo decoder is I n (TPCD) = 2 × n 2 BCH × q while an equivalent full parallel 1024-LDPC decoder would have I n (1024-LDPC) = n LDP C × q × d v where d v represents the variable node degree. Consequently, as long as d v >2, the following inequation is verified: I n (T P CD) < I n (1024 -LDP C).

CONCLUSION

High throughput TPC decoder architecture complexity is made prohibitive by the amount of memory usually required for data interleaving and pipelining. In this article, we proposed an innovative product code matrix decoding scheduling which enables any interleaving resource to be removed. The resulting architecture requires a full-parallel SISO decoder able to decode n symbols in one clock period. Such a SISO decoder architecure is described and includes a new optimized parallel sorting network. ASIC based-logic synthesis showed the better efficiency of the proposed architecture. Actually, compared to a previous architecture, the area is reduced while the throughput is the same. Finally, in order to enhance parallelism rate and throughput, a slightly different scheduling is proposed. With such a scheduling, the maximum parallelism rate O(n 2 ) can be achieved. An area estimation showed that a (32,26) 2 BCH code can be decoded at 33.7Gb/s with an estimated silicon area of 10µm 2 .

Fig. 1 .

 1 Fig. 1. Proposed parallel decoding scheduling of a product code matrix

Fig. 2 .

 2 Fig. 2. Previous TPC decoder architecture (a) and proposed full-parallel SISO based TPC decoder architecture (b)

Figure 3

 3 Figure 3 depicts the architecture of the full-parallel SISO decoder. It was firstly designed totally combinatorial, then, a critical path study enabled the insertion of pipeline stages within the structure.

Fig. 3 .

 3 Fig. 3. Combinatorial version of the full-parallel SISO decoder

Fig. 4 .

 4 Fig. 4. BCH(7,4) code: (a) Parity check matrix (b) Parity check equations (c) Syndrome parallel computation implementation

Fig. 5 .

 5 Fig. 5. Optimized sorting network for least reliable bits selection

Table 2 .

 2 Comparison of sequential and parallel (32,26) BCH SISO decoder performances Table

				SISO decoder		Seq-based
	s	1	2	3	4	5	3
	f max (Mhz) 222 385 526 690 741	700
	A (Kgates)	47	32	33.8	39	36.2	200
	T in (Gb/s)	7.1 12.3 16.8 22.1 23.7	22.4
	T out (Gb/s)	4.7	8.1 11.1 14.6 15.6	14.8
	η(Mb/s/gate) 0.1 0.25 0.33 0.37 0.43	0.07


Camille Leroux

Christophe Jego

Patrick Adde

Michel Jezequel

On the higher ef ciency of parallel Reed-Solomon turbo-decoding

In this paper, we demonstrate the higher hardware ef ciency of Reed-Solomon (RS) parallel turbo decoding compared with BCH parallel turbo decoding. Based on an innovative architecture, this is the rst implementation of fully parallel RS turbo decoder. A performance analysis is performed showing that RS Block Turbo Codes (RS-BTC) have decoding performance equivalent to Bose Ray-Chaudhuri Hocquenghem-Block Turbo Codes (BCH-BTC). A ratio between the decoder throughput and the decoder area is used to show the higher ef ciency of the RS full parallel turbo decoder. Finally an implementation of a (31,29) 2 RS block turbo decoder on a high performance board including 6 Xilinx Virtex5 FPGAs is detailed. The resulting turbo decoder has an information throughput above 6Gb/s while the working frequency is only 45MHz. It shows that RS BTC are an attractive solution for low cost Gb/s ber optical communications.

I. INTRODUCTION

Since their invention, turbo codes and block turbo codes [START_REF] Berrou | Near shannon limit errorcorrecting coding and decoding: Turbo-codes. 1[END_REF] [START_REF] Pyndiah | Near optimum decoding of product codes[END_REF] have been used in most challenging telecommunications systems such as cellular communication systems, digital video broadcasting or wireless metropolitan area networks. It has been demonstrated that block turbo codes (BTC) are well adapted codes for a very high speed context [START_REF] Chi | High speed vlsi architecture design for block turbo decoder[END_REF]. A high throughput BCH turbo decoder implementation was proposed for Optical Transport Networks (OTN) [START_REF] Tagami | A 3bit soft-decision ic for powerful forward error correction in 10-gb/s optical communication systems[END_REF]. However, in contrast to OTN, some very high speed applications such as Passive Optical Networks (PON) require a low-cost optical infrastructure with good performance. A PON is point-to-multipoint optical network in which passive splitters are used to connect a single Optical Line Termination (OLT) to many users. In such a context, Forward Error Correction (FEC) were recently introduced to compensate the signal degradation due to low cost optical components and to increase the number of users connected to the same OLT [START_REF] Briand | Forward error correction in wdm pon using spectrum slicing[END_REF]. In PONs, even if decoding performance constraints are not as strict as in OTN, increasing the coding gain reduces the cost of the infrastructure per user. Current normalized solutions (B-PON,G-PON) include an optional (255,239) RS code giving a 3dB coding gain at 2.5Gb/s. Next generation PONs will use Wavelength Division Multiplexing (WDM) technology in order to increase both data rate (above 10Gb/s) and the number of users. In such a context, FECs with higher coding gain and increased throughput will be needed. So far, no realization or architecture of a very high speed BTC decoder has been proposed for PONs. In this article, we show that BTCs present notable performance improvement compared to the (255,239) RS code. It is also demonstrated that parallel RS turbo decoding This work was supported with funds from the Brittany Region under the competitiveness pole Interaccess gives better hardware ef ciency compared to parallel BCH turbo decoding.

This paper rst recalls the basic principle of decoding for product codes: their construction and turbo decoding. In section III, we propose a performance study highlighting the good performance of BTC decoding compared to (255,239) RS. Section IV presents the highly parallel architecture of the BTC decoder. In section V, a complexity and throughput analysis shows the better hardware ef ciency of RS turbo decoding. Finally, section VI describes a prototype of an RS(31,29) 2 turbo decoder in an FPGA experimental setup.

II. BTC CODING AND DECODING PRINCIPLE

A product code is a concatenation of systematic linear block codes. The product code inherits the properties of the elementary codes that it is composed of. Let us consider two identical systematic linear block codes C having parameters (n; k; ), where n and k stand for code length, the number of information symbols and the minimum Hamming distance respectively. The parameters of the resulting product code are given by: n p = n 2 , k p = k 2 , p = 2 and R p = R 2 (code rate). Thus, it is possible to construct powerful product codes using linear block codes. The turbo decoding process involves sequentially decoding the rows and columns of the product code matrix by exchanging soft information. This decoding is called Soft Input Soft Output (SISO) decoding [START_REF] Pyndiah | Near optimum decoding of product codes[END_REF].

The SISO decoding algorithm can be summarized as follows: do the syndrome based algebraic decoding of the T v test vectors that have been built by inversions of the Lr least reliable symbols in the received word [R 0 ] it . The Lr least reliable symbols have been previously searched for. After that, for each corrected test vector, compute the square Euclidean distance between [R 0 ] it and the test vector considered. Select the Decided codeWord (DW) having the minimal distance from [R 0 ] it and choose Cw competitor words having the closest distance to [R 0 ] it . Finally, compute the soft output information

[R 0 ] it+1 = [R] it + it [W ]
it for each symbol where [W ] it is the extrinsic information and it is a coef cient that allows decoding decisions to be damped during the rst iterations. It should be noted that decoding parameters Lr, T v, and Cw has a notable effect on performance. Decoding a BCH or RS code only differs in the algebraic decoding phase.

III. DECODING PERFORMANCE OF BTC VERSUS RS CODE

In this section, the BTC contribution in PONs is highlighted by comparing different BCH-BTC and RS-BTC with a correction power of one to the widely used (255,239) RS code. SISO decoding complexity is particularly increased for correction powers larger than one. Indeed, higher correction power codes require higher complexity algorithm for algebraic decoding such as the Berlekamp-Massey algorithm [START_REF] Berlekamp | Algebraic Coding Theorie[END_REF]. On the contrary, algebraic decoding for a correction power of one enables a direct computation of both locator and error estimator polynomials. Since PONs require low complexity systems, we choose to only consider BTCs with a correction power of one.

Figure 1 gives the decoding performance of different BTCs compared with the (255,239) RS over a Gaussian channel with an On-Off Keying (OOK) mapping. The OOK uncoded curve is also represented. BTC decoding uses the Chase-Pyndiah algorithm with 5 least reliable bits (Lr), 16 test vectors (T v) and 3 concurrent words (Cw). The soft information is quantized with at least 5 bits ensuring that performance is very close to the oating point model. The comparison between code performance is thus made more consistent. In a general manner, BTCs offer a higher coding gain than (255,239) RS. Decoding performance depends on the type of elementary code (BCH or RS), the code size n and the code rate R. Regarding codes with an equivalent rate (e:g: (31,29) 2 RS and (128,120) 2 BCH), BCH-BTC have a better slope than RS-BTC but are limited in terms of asymptotic performance. Indeed, performance of BCH product codes is penalized by their asymptotic bound. In contrast, RS product codes push down the error oor and the corresponding performance has no change in slope [START_REF] Zhou | Low-complexity highrate reed-solomon block turbo codes[END_REF]. Thus, RS-BTC tend to be more ef cient in low Bit Error Rate (BER) area as required in optical transmission systems.

In the light of coding gain values, ve codes remain good candidates in terms of decoding performance: (32,26) 2 BCH, (64,57) 2 BCH and (128,120) 2 BCH converge with the same trend having a fairly similar slope. (15,13) 2 RS and (31,29) 2 RS have good asymptotic performance with coding gain around 7.5dB at BER=10 10 . Architectural issues will determine which code is more ef cient in terms of complexity for equivalent performance.

IV. ULTRA HIGH SPEED ARCHITECTURE

In this section, a highly parallel architecture of the turbo decoder involving a duplication of elementary decoders connected by interconnection networks is described.

A. Full-parallel architecture of the turbo-decoder Figure 2 depicts a full-parallel architecture for the product code turbo decoding proposed in [START_REF] Jego | Full-parallel architecture for turbo decoding of product codes[END_REF]. The major advantage of this full-parallel architecture is that it enables the memory block of 4 q n 2 symbols between each half-iteration to be replaced by simple interconnection networks. Each duplicated module is dedicated to one iteration. However, it is possible to process several iterations by a same module. In our approach, 2n elementary decoders and 2 connection networks are necessary for one module. In fact, the full-parallel turbo decoder complexity mainly depends on the complexity of the elementary decoder and the code size n. The SISO decoder architecture shown in gure 3 is structured in three pipelined stages identi ed as reception, processing and transmission units. The reception and transmission units process one symbol per clock period while the processing unit process T v test vectors. The reception unit computes syndromes S 0 , S 1 and locate the Lr least reliable bits of the word received [R 0 ] it . This unit is also in charge of the decoder sequencing by generating control signals. The processing unit computes the error position X i and value E i of the currently processed test vector from the previously computed syndromes S 0 (T v i ) and S 1 (T v i ). The Euclidean distance values (amso called metrics) M (T v i ) of each vector is then calculated enabling the D-C bloc to select the decided word (the one having the minimum metric value) and the competitor ones in order to generate the new reliability [F ] it . The transmission unit computes the scaled extrinsic information [W ] it and the soft output [R 0 ] it+1 . A new (m q) bits symbol is then transmitted during each clock period. q is the number of quantization bits of the soft information. The decoding process needs to access the [R] it and [R 0 ] it values during the three decoding phases. For this reason, these words are implemented in six Random Access Memories (RAM) of size n m q controlled by a nite state machine. Since the error position X i is computed in GF (32), the RAM is also adressed in GF (32). In our architecture, this SISO decoder is the main elementary block of the BTC decoder, consequently, low-complexity SISO decoders are required.

B. Elementary SISO decoder

V. COMPLEXITY AND THROUGHPUT ANALYSIS OF THE

FULL-PARALLEL BTC DECODER Increasing throughput regardless of turbo decoder complexity is not relevant. In order to compare the throughput and complexity of RS and BCH turbo decoders, the ef ciency of the parallel BTC decoder is de ned as

= T C (1)
T is the throughput (b=s) and C the complexity (gates) of the design. An ef cient architecture will have a high ratio meaning a high throughput with low hardware complexity. This study aims to determine ef ciency for both BCH-BTC and RS-BTC in order to compare them.

A. BTC decoder throughput analysis

In a fully pipelined architecture, the throughput of the block turbo decoder can be de ned as

T = P R f 0 ( 2
)
where P is the parallelism degree and corresponds to the number of generated bits per clock period t 0 , R is the code rate and f 0 = 1 t0 the maximum frequency of an elementary SISO decoder. Ultra high throughput can be reached by increasing these three parameters.

R is a parameter that exclusively depends on the code considered. Thus, using codes with a higher code rate (e:g: RS codes) would provide improved throughput. In a full-parallel architecture, a maximum throughput is obtained by duplicating n elementary decoders generating m soft values per clock period. The parallelism degree is then expressed as

P = n m (3)
with m the number of bits per symbol. Considering an RS code with a code size n RS , m RS = log(n RS +1) whereas BCH codes only have m BCH = 1. Therefore, enhanced parallelism degree can be obtained by using non-binary codes (e:g: RS codes) with larger n value. Finally, in a high speed architecture, each elementary decoder has to be optimized in terms of working frequency f 0 . This is accomplished by including pipeline stage within each elementary SISO decoder as shown in gure 3. In the considered architecture, RS and BCH SISO decoders with equivalent code size have equivalent working frequency f 0 since RS decoding is performed by introducing some local parallelism at symbol level. This result was veri ed during logic syntheses. The main drawback of pipelining elementary decoders is the extra-complexity generated by internal memory requirement (registers and RAM). Since RS codes have higher P and R for equivalent f 0 , RS turbo decoder can potentially reach a higher data rate than BCH. However, the increase in throughput can not be considered regardless of the turbo decoder complexity.

B. BTC decoder complexity analysis 1) Computation resource complexity: The computational resources of a SISO decoder are split into three pipelined stages. The reception and transmission stages have a complexity in O(log(n)). For these two stages, moving from a BCH code to a RS code, both complexity and throughput are increased with a factor log(n RS + 1). As a result, ef ciency is constant in these parts of the decoder. However, the processing stage has a hardware complexity in O(T v). Consequently, the increase in the local parallelism rate has no in uence on the area of this stage and thus increases the ef ciency of a RS SISO decoder.

In order to verify those general considerations, BCH SISO decoder area was estimated thanks to a complexity model which can derive an estimation of the gate count for any code size and any decoding parameter set [START_REF] Leroux | Towards gb/s turbo decoding of product code onto an fpga device[END_REF]. RS turbo decoders for code (63,61) 2 RS, (31,29) 2 RS and (15,13) 2 RS were described in HDL language and synthesized. Logic syntheses were performed using Synopsys Design Compiler with a ST-microelectronics 90nm CMOS process. All designs were clocked at 100MHz. Table I shows the higher ef ciency of the computational resources among the parallel BTC decoder. Indeed, when comparing (31,29) 2 RS and (63,61) 2 RS with the (128,120) 2 BCH code, it can be noted that RS codes enable higher throughput with a lower computational resource complexity. The same observation can be done considering (15,13) 2 RS and (32,26) 2 BCH codes; the throughput is doubled while the complexity is divided by 1.8. RS turbo decoding appears to use computational resources in a more ef cient manner. However, even if our architecture enables interleaver memory to be removed, more than a half of a parallel BTC decoder is composed of internal memory.

2) Memory resource complexity: A half-iteration of a parallel block turbo decoder contains n RAM banks of n m q bits. The internal memory complexity of a parallel decoder for a half-iteration can be approximated by

S RAM ' n 2 m q (4)
where is a technological parameter specifying the number of equivalent gate counts per memory bit. Using equation 3, it can also be expressed as

S RAM = P 2 m q (5)
Calculating the SISO memory area for both BCH RS gives the following ratio:

S RAM (BCH) S RAM (RS) = m RS = log(n RS + 1) (6)
It shows that RS block turbo decoders have lower memory complexity for a given parallelism rate P . This was con rmed by memory area estimations results showed on Figure 4. RAM area of BCH and RS turbo decoders for a half-iteration and different parallelism degrees is plotted using a memory area estimation model provided by ST-Microelectronics. We can observe that higher P (i:e: higher T ) can be obtained with less memory when using an RS turbo decoder. Full-parallel decoding of RS codes appears to be more memory-ef cient than BCH code turbo decoding.

3) Ef ciency comparison: Table II sumarizes the code rate R, the parallelism rate P , the throughput T (Gb:s 1 ), the complexity C (kgates) and the ef ciency (kb:s 1 :gate 1 ) of a half-iteration of parallel BTC decoder for each studied code. An average ratio of 3.5 between RS and BCH decoders ef ciency is observed. In some cases, RS codes enable higher throughput with lower complexity. The good compromise between performance, throughput and complexity clearly makes RS codes good candidates for high throughput applications such as next generation PON technologies.

VI. FPGA IMPLEMENTATION

The RS(31,29) 2 code was selected to be implemented on a high performance platform. The board includes 6 XilinxVirtex5 LX330 FPGAs [10]. An embedded memory containing 40 encoded and noisy product code matrices is used to generate input data towards the turbo decoder. One decoding iteration was implemented on each FPGA resulting in a 6 full-iteration block turbo decoder. Each decoder uses information quantized on 5 bits with 8 test vectors and 1 concurrent word. These reduced parameter values enable a decrease in the area for a performance degradation less than 0.5dB. The occupation rate of each FPGA is slightly higher than 50%. Input data are clocked at f =45MHz resulting in an input throughput of T in =7Gb/s. Taking into account the code rate R=0.875, the output throughput becomes T out =6.13Gb/s. The current working frequency is limited by the available bandwidth between two FPGAs. A full decoding iteration can operate above 50MHz.

Moreover, no back-end optimization has yet been performed. Using partitioning or intelligent place and route strategy will again increase working frequency and throughput above 10Gb/s.

VII. CONCLUSION

This article shows the advantages of RS product codes decoding in an ultra high speed context. We rst have highlighted the good performance of RS-BTCs compared to both BCH-BTC and (255,239) RS. Then the better hardware ef ciency of RS parallel turbo decoding has been demonstrated especially in terms of internal memory requirements. Compared to BCH, the RS turbo decoder can reach a higher data rate for equivalent complexity. Finally, an FPGA implementation of a (31,29) 2 RS parallel turbo decoder shows that RS turbo decoding can reach several Gb/s. To the best of our knowledge, this is the rst multi-gigabit implementation of a RS turbo-decoder. The complexity study showed that most of the area of the block turbo decoder is composed of SISO decoder internal memory resources. Consequently a study for proposing architectures with low-memory requirements in BTC decoding is in progress.

Fig. 1 .

 1 Fig. 1. BTC and (255,239) RS decoding performance

Fig. 2 .

 2 Fig. 2. Full-parallel decoding of product codes

Fig. 3 .

 3 Fig. 3. RS SISO decoder architecture

Fig. 4 .

 4 Fig. 4. Comparison of internal RAM complexity


Camille Leroux

Christophe Jego

Patrick Adde

Michel Jezequel

Toward Gb/s turbo decoding of product code onto an FPGA device

This paper presents the implementation, on an FPGA device of an ultra high rate block turbo code decoder. First, a complexity analysis of the elementary decoder leads to a low complexity decoder architecture (area divided by 2) for a negligible performance degradation. The resulting turbo decoder is implemented on a Xilinx Virtex II-Pro FPGA in a communication experimental setup. Based on an innovative architecture which enables the memory blocks between all half-iterations to be removed and clocked at only 37.5 MHz the turbo decoder processes input data at 600Mb/s. The component code is an extended Bose, Ray-Chaudhuri, Hocquenghem (eBCH(16,11)) code. Ultra high-speed block turbo decoder architectures meet the demand for even higher data rates and open up new opportunities for the next generations of communication systems such as fiber optic transmissions.

I.

INTRODUCTION

In telecommunications, forward error correction (FEC) is a system of error control that improves digital communication quality. A recent development in error correction is turbo coding. Block turbo codes (BTC) are an alternative solution to convolutional turbo codes (CTC) introduced in 1993 by C.Berrou [START_REF] Berrou | Near Shannon limit error-correcting coding and decoding : Turbo-codes (1)[END_REF]. BTC were proposed by R. Pyndiah [START_REF] Pyndiah | Near optimum decoding of product codes : Block Turbo Codes[END_REF] in 1994. The coding scheme uses a serial concatenation of systematic linear block codes (product codes introduced by P. Elias [START_REF] Elias | Error-free coding[END_REF]) and the decoding is carried out using soft input-soft output (SISO) elementary decoders. Recently, BTC have been included in the specifications of the Wireless Metropolitan Area Networks (IEEE 802.16) standard to increase transmission rates and/or to guarantee the Quality of Service (QoS). Some processes like optical transmission or data storage require ultra high speed above 10 Gb/s data coding and decoding. The first codes used in optical transmission were the well-known Reed-Solomon codes [START_REF] Azadet | Equalization and FEC techniques for optical transceivers[END_REF] which allow respectable throughput for a Net Coding Gain (NGC) up to 6dB. In such contexts, BTC are an attractive solution since product codes structure present a high parallelism rate and a theoretical NCG of 10dB [START_REF] Sab | Block turbo code performances for longhaul DWDM optical transmission systems[END_REF] [START_REF] Mizuochi | Recent Progress in Forward Error Correction for Optical Communication Systems[END_REF]. However, FEC decoders achieving multi-gigabit throughputs require new massively parallel architecture with reduced complexity.

In BTC, the iterative decoding algorithm of a matrix (product code) involves performing the successive decoding of all rows and all columns (two half-iterations). To increase the data rate, it is possible to perform all the rows (columns) in parallel during a half-iteration. However in classical approaches [START_REF] Kerouedan | Implementation of a Block Turbo Decoder on a Single Chip[END_REF], a reconstruction of the data is necessary between two successive half-iterations. This requires a large amount of memory (up to 75% of the design) and limits the implementation possibilities. In [START_REF] Jego | Full-parallel architecture for turbo decoding of product codes[END_REF], an innovative architecture that enables the memory blocks between each half-iteration to be removed has been proposed. In such an architecture, the remaining complexity is in the decoding processors: the number of required SISO decoders is DEC n = 2×it×n, where it and n are the number of decoding iterations and the code size respectively. Therefore, implementing a full parallel BTC decoder requires to decrease the complexity of the elementary SISO decoder architecture.

This paper is organized as follows. Section II recalls the basic principles of decoding for product codes: their construction and the turbo decoding process. In section III, we propose a complexity and performance analysis of the elementary decoder which allows a rapid and efficient estimation of the decoder complexity. Finally, in section IV, an implementation of the resulting turbo decoder onto a FPGA target is presented.

II. BTC CODING AND DECODING PRINCIPLES

In this section, the concept of product codes, their construction and the principle of the decoding algorithm are presented.

A. Construction of product codes

The concept of product codes is a simple and efficient method to construct powerful codes with a large minimum Hamming distance δ using conventional linear block codes.

Let us consider two identical systematic linear block codes C having parameters (n,k), where n and k stand for code length and number of information symbols respectively. The product code P=C×C is obtained by placing k 2 information bits in a matrix of k rows and k columns, coding the k rows and k columns using code C. It is shown that all n rows are codewords of C exactly as all n columns. Furthermore, the parameters of the resulting product code P are given by n p =n 2 , k p =k 2 and the code rate R p is given by R p =R 2 . Thus, it is possible to construct powerful product codes using linear block codes. As a general rule, the more powerful a code, the more difficult the decoding process.

B. SISO decoding of product codes

Product code decoding involves sequentially decoding rows and columns using SISO decoders. Repeating this soft decoding over several iterations enables a decrease of the Bit Error Rate (BER). It is known as the block turbo decoding process. Each decoder has to compute soft information [R'] k+1 from the channel received information

[R'] k . 6-Compute reliability [F] k for each symbol of the DW, 7-Compute extrinsic information [W] k =[F] k -[R'] k for each symbol of the DW. 8-Add extrinsic information (multiplied by α k ) to the channel received word, [R'] k+1 =[R] k +α k [W] k
An α k coefficient allows us to damp decoding decisions during the first iterations. It should be noted that decoding parameters Lr, Tv, and Cw has a notable effect on performance.

III. COMPLEXITY AND PERFORMANCE ANALYSIS

FOR eBCH SISO DECODERS Syntheses for the complexity estimations were performed using the Synopsys tool with an STMicrolectronics 0.09 μm CMOS process target. Elementary decoders are clocked at f=500MHz. BER performance was simulated using C-ANSI models of a turbo decoder for the product codes eBCH(16,11)² and eBCH(32,26)² after 6 iterations.

A. Complexity analysis of BCH SISO decoders

All the soft information within the decoder is quantized and processed with Q bits (1 sign bit and Q-1 reliability bits). The SISO decoder architecture is structured in three pipelined stages identified as reception, processing and emission units. Each stage processes n symbols in n clock periods. The resulting latency is then equal to 2n clock periods. The reception unit computes the syndrome S 0 and the Lr least reliable bits of the word received [R'] k . The processing unit computes the syndrome of the Tv test vectors and their metric values. Finally, the emission unit calculates new reliabilities from the metrics of the decided word and the Cw concurrent words. Extrinsic information [W] k and soft output [R'] k+1 are also processed during the same clock period. A new Q-bits symbol is then transmitted at each clock period. The decoding process needs to access the [R] k and [R'] k values during the three decoding phases. For this reason, these words are implemented in Random Access Memories (RAM) of size Q*n.

The proposed SISO decoder is composed of twelve processing parts. Running conventional decoder designs through logic synthesis showed that only four parts were critical in terms of logical gate complexity (75% of the area). As a result, our study is focused on these parts. One of these parts is the alpha multiplication unit. In classical architectures, it is implemented as a conversion table. The input can be multiplied by 0.55 < α k < 0.75, the value depending on the current iteration. Keeping α k = 0.5 for each iteration enables the unit to be removed since the multiplication becomes a simple bit shifting. Therefore, the elementary decoder area is decreased by 8%. The induced loss of performance Δ α is very low (0<Δ α <0.1 dB). Consequently, the complexity analysis will now be focused on the three remaining parts. By analyzing the architecture of these critical parts, five parameters appear to directly affect their complexities. Table 1 sums up the order of complexity of the three critical parts that depends on the parameters introduced in section II. B.

Reliability computation O(log(n)) O(Q) O(Lr) O(Tv) O(Cw)
Decoding parameters Lr, Tv, Cw, as well as the code size n and the number of quantization bits Q has a direct impact on the decoder complexity (area or number of logical gates). Considering a code size n, let us define a set p i of decoding parameters:

p i = { Q i , Cw i , Tv i , Lr i }. ( 1
)
Varying p i , directly affects both the hardware complexity and the decoding algorithm performance. Increasing these parameter values improves performance while the complexity increases. The purpose of our analysis is to be able to compute easily the complexity of a SISO decoder for any set of parameters p i with reasonable accuracy. Considering a code size n, the most favorable configuration is:

p 0 ={Cw 0 =3,Q 0 =5,Tv 0 =16,Lr 0 =5}. ( 2
)
Actually, increasing p 0 parameters values would increase complexity without significantly improve performances. For this reason, this configuration is the reference for our decoder architecture complexity. Synthesis showed that, in this case, the four critical parts represent 75% of the decoder area whatever the code size n. In addition, assuming that the remaining 25% of the decoder is almost not affected by the variation of a set p i (as verified during syntheses), it can be demonstrated that the SISO decoder complexity C pi (n) can be expressed as: [START_REF] Elias | Error-free coding[END_REF] where C' pi (n) is the cumulated complexity of the four critical parts in terms of logical gates for a parameter set p i .

C pi (n) = 1/3 (C' p0 (n)) + C' pi (n) ,
Synthesizing generic descriptions of the critical parts and carrying out a multiple linear regression analysis led to an expression of C' pi (n) only depending on the decoding parameters. This expression represents the cumulated complexity C' pi (n) of the four critical parts in terms of logical gates for a parameter set p i .

C' pi (n) = 462(Cw i -1) + 261(log(n)-4) + 183(Q i -4) + 55(Tv i -4) + 46(Lr i -2) + 1019 .

(4) The model's accuracy was measured a posteriori. The maximum and average errors (between model and synthesis results) are 8% and 2.5% respectively. Table II gives four examples of estimated complexity for code size n=16 and 32. Using this model immediately gives the complexity of an eBCH SISO decoder for any set of decoding parameters. Therefore, taking into account the implementation and performance constraints, it becomes very straightforward to select a code size n and a decoding parameter set p i .

B. Selection of a parameter set and a code size

Simulations showed that for a small size of product code (eBCH(32,26)² and eBCH(16,11)²), the performance degradation associated with the particular set p 1 ={Cw=1, Q=4, Tv=4, Lr=2} was only about 0.3 dB at BER=10 -4 . Furthermore, for n=16, simulations showed that the loss of performance became negligible for SNR > 4dB. It can be seen that decoding parameters in p 1 have low values. The complexity of the SISO decoder is then highly reduced for reasonable performance loss. Using (3) and ( 4), C p1 (16) = 2055 logical gates and C p1 (32) = 2865 logical gates were obtained. Compared with the decoder complexity reference Cp 0 (16) and Cp 0 (32), gains of 50% and 36% were achieved respectively.

A block turbo decoder designed according to the complexity analysis results has to be integrated. Currently, a typical hardware design approach is to use an FPGA development board to first prototype the turbo decoder design and its experimental setup. The low cost Virtex II-Pro XUP [10] development system from Digilent was selected for our experimentation. These boards contains a Xilinx Virtex II-Pro XC2VP30 FPGA device with 13696 slices. Preliminary syntheses show that only a half-iteration of the eBCH(32,26)² block turbo decoder would fit onto the Virtex II-Pro XC2VP30 device. Indeed, some elements of the experimental setup have to fit onto the same FPGA device as the block turbo decoder. In the case of BCH(16,11)², up to 3 half-iterations (48 SISO decoders) can be implemented on the same device. For this reason, the BCH(16,11)² was finally chosen for our experimentation. The parameter set p 1 ={Cw=1, Q=4, Tv=4, Lr=2} was selected for each elementary decoder.

IV. IMPLEMENTATION OF A BLOCK TURBO DECODER IN AN ULTRA HIGH RATE COMMUNICATION SETUP

A. Experimental setup

The experimental setup is composed of two identical development boards XUP linked with a Serial ATA communication bus. BER measurement facilities are implemented in order to rapidly verify the decoding performance. Each board contains a Xilinx XC2VP30 device that can transmit data at a 2.4 Gbits/s rate. Indeed, encoded noisy data are sent from the transmitter FPGA to the receiver FPGA using the high speed Xilinx Aurora protocol. Each board has its own digital clock management system operating at 50MHz. Synchronization between the two boards is carried out by Aurora protocol control signals. The Aurora protocol is clocked at f 1 =75MHz and the rest of the setup is clocked at f 0 =37.5MHz. Figure 1 shows the different components of the communication setup implemented onto the FPGA.

1

) The components implemented on the transmitter FPGA device

A Pseudo Random Generator (PRG) sends out eleven pseudo random data streams at each clock period (f 0 ). It is composed of eleven different LFSR. An eBCH(16,11) 2 encoder processes the eleven data streams in parallel. This innovative architecture avoid the use of memory between row and column encoding [START_REF] Jego | Full-parallel architecture for turbo decoding of product codes[END_REF]. Classical sequential encoders are cascaded with a parallel encoder. 256 data (equivalent to a matrix 16×16) are generated in 16 clock periods (f 0 ). The noise generator models 16 uncorrelated White Gaussian Noise (WGN) samples and adds them to the previously encoded data [START_REF] Danger | Efficient FPGA Implementation of Gaussian Noise Generator for Communication Channel Emulation[END_REF]. Each output sample is a 4 bit vector resulting in 64 bits to be sent in 1 clock period (f 0 ). The Signal to Noise Ratio (SNR) is controllable via on-board switches 0<SNR<15.75dB with a pitch of 0.25dB. The Aurora protocol emission module handles a set of control signals. It receives 64 data in 2 clock cycles and sends 32 data every clock cycle (f 1 ). The output rate is then 2.4Gb/s.

2) The components implemented on the receiver FPGA device

The Aurora protocol reception module receives data at 2.4 Gbits/s and sends out 64 bits every two clock cycles (f 1 ). The turbo decoder is composed of 32 SISO (16 SISO decoders per half-iteration) and two omega networks used to route data between half-iterations. More information about the decoder architecture and the omega network can be found in [START_REF] Jego | Full-parallel architecture for turbo decoding of product codes[END_REF]. Data arrive at 2.4Gb/s while the working frequency is only 37.5 MHz. The same PRG is also implemented in the receiver. It generates the exact same data as in the transmitter in order to compare data before and after decoding. A BER block is finally used to measure the error rate comparing data from the PRG and the decoder output. It guarantees a minimum of 1000 errors before outputting the BER value. This value is then displayed on an LCD module. The minimum reliable BER value is 10 -9 .

B. Toward very high rate implementation

The purpose of this first implementation is to show that a block turbo decoder can effectively work without memories between half-iterations at high throughput. Clocked at only 37.5MHz, the turbo decoder processes input data at 600Mb/s. This frequency is limited by the communication protocol. The turbo decoder can actually perform up to 70MHz on this target, which corresponds to 1.12 Gb/s. Using an FPGA device optimized for high-performance logic would lead to even higher frequency. Regarding the output rate, it is defined as:

D out = P f R .
(5) P is the parallelism rate (max(P)=n), f the decoder frequency and R the code rate. In our case, P=16, f=f 0 =37.5MHz and R=0.473, the resulting throughput is then 284Mb/s. Several solutions exist to increase the throughput, the more straightforward is to use a larger code (in order to increase P) with a larger rate R. For instance, assuming we are using an eBCH(32,26) 2 at frequency f 0 =70MHz, the input and output data rates become 2.24Gb/s and 1.48Gb/s respectively. In our architecture, SISO decoders process data sequentially. Designing SISO decoders which decode several data in one clock period, as in [START_REF] Cuevas | Very powerful block turbo codes for high data rates applications[END_REF], would again improve throughput and with a limited complexity overhead. Moreover, enhancing our study to non binary component codes like RS codes [START_REF] Piriou | Efficient architecture for Reed Solomon block turbo code[END_REF] can increase data rate even more. The turbo decoder was synthesized and implemented on a Virtex II Pro FPGA using Xilinx ISE 7.1i tools. The decoder occupied 7300 slices. So far, one iteration (32 SISO decoders and 2 omega networks) has been fully implemented. The available target (xc2vp30) was insufficient to implement several iterations. Duplicating the decoders simply requires a larger FPGA target. Implementing a 6iterations full-parallel turbo decoder represents 43800 FPGA slices with a maximum throughput. Such a design can for instance, fit onto a Xilinx Virtex 4.

V. CONCLUSION

This article shows how we implemented a memory free, high-throughput, full-parallel, block turbo decoder on a FPGA target. In such parallel architectures, it is necessary to use low complexity SISO decoders. We first proposed a complexity analysis for the eBCH(16,11) SISO decoder. The complexity expression gives a rapid estimation of the SISO area, for a fixed set of decoding parameters. Then, depending on the required level of performances, it becomes easy to decide on a set of parameters to implement. This analysis led to a low complexity SISO decoder (-50%) to be duplicated in the parallel turbo decoder. Next, we describe the experimental setup designed to test the turbo decoder. Using a more efficient communication protocol the turbo decoder can process input data at 1.2Gb/s. Using a larger code, with a higher rate and parallel SISO decoders, would again, increase the data rate. Moreover non binary codes like RS codes enable even higher throughputs to be reached.

Figure 1 .

 1 Figure 1. Multi-gigabit experimental setup

  For each test vector, compute the square Euclidian distance (metric) M i (i=0,…,Tv n -1) between [R'] k and the considered test vector. 5-Select the Decided Word (DW) having the minimal distance with [R'] k and choose Cw concurrent words having the closest distance with

	previous half-iteration computed information [R'] k . A SISO
	decoder of an eBCH code based on the Chase-Pyndiah
	algorithm [2][9] is concisely summarized below:
	1-Search for the Lr least reliable binary bits and
	compute the syndrome S 0 of [R'] k ,
	2-Generate Tv test vectors obtained by inverting some
	of the Lr least reliable binary symbols,
	3-Binary decoding of each test vector using the
	syndrome computation,
	4-
	[R] and the

TABLE I .

 I ORDER OF COMPLEXITY OF THE THREE CRITICAL PARTS

	Parts	n	Q	Lr	Tv	Cw
	DW-Cw sorting	O(log(n)) O(Q) O(Lr) O(Tv) O(Cw)
	Least reliable sorting		O(Q) O(Lr) O(Tv)

TABLE II .

 II

		COMPLEXITY IN TERMS OF LOGICAL GATES OF THE
		CRITICAL PARTS
	Parameter set p i	n Q Lr Tv Cw C' pi (n) C pi (n)
	p 0	16 6 5 16 3 3107 4143
	p 1	16 4 2	4	1 1019 2055
	p 0	32 6 5 16 3 3368 4491
	p 1	32 4 2	4	1 1742 2865