Camille Leroux
email: camille.leroux@telecom-bretagne.eu

Christophe Jégo

Patrick Adde

Michel Jézéquel

High-throughput Block Turbo Decoding: From Full-parallel Architecture to FPGA Prototyping

Keywords: Block turbo decoding, Full-parallel architecture, Complexity analysis, FPGA implementation

) code. Some solutions to reach even higher data rates are finally presented.

Introduction

In telecommunications, forward error correction (FEC) is a system of error control that improves digital com-munication quality. Error correction encoding is the addition of redundancy into the binary information sequence that is to be transmitted over the communication channel. This redundancy allows the error correction decoder to detect and/or to correct the effects of noise and interference encountered in the transmission of the information through the communication channel. Turbo coding was a powerfull improvement in error correction systems [1]. This family of codes consists of two key design innovations: concatenated encoding and iterative decoding. Soft Input Soft Output (SISO) decoders are used in the iterative decoding process. A SISO decoder both receives soft decision data and produces soft decision output. The general concept of the iterative SISO decoding of concatenated convolutional codes has been extended to product codes [START_REF] Pyndiah | Near optimum decoding of product codes[END_REF] and LDPC codes [START_REF] Gallager | Low density parity check codes[END_REF]. Moreover, the principle of turbo processing has been extended into new receiver topologies such as turbo detection, turbo equalization, turbocoded modulation, turbo MIMO, etc. Since 1999, turbo codes have been adopted by several applications. They are particularly attractive for cellular communication systems and have been included in the specifications for both the UMTS and CDMA2000 third-generation cellular standards. Similarly, turbo codes were chosen in the field of Digital Video Broadcasting (DVB) and Wireless Metropolitan Area Networks (IEEE 802. [START_REF] Elias | Error-free coding[END_REF]) to increase transmission rates and/or to guarantee Quality of Service (QoS). Currently, research is under way to use turbo codes to protect data stored on hard drive or DVD and in fiber optical transmission. Fiber optical communications are an important technology in supporting broadband networking. The earliest FEC for optical communication [START_REF] Azadet | Equalization and fec techniques for optical transceivers[END_REF] employed the well known Reed-Solomon (RS) codes to recover the degradation in bit error rate (BER) due to the effects of fiber nonlinearity and polarization-dependent phenomena. The standard interfaces and rates are specified in the ITU-T G.709 for Optical Transport Networks (OTN). A G.709 OTN frame includes an RS(255,239) code that helps reduce the number of transmission errors on noisy links, which enables the increase in transmission capacity. A net coding gain of around 6dB is provided by the RS(255,239) code. During the last few years, more powerful FECs have been studied to increase the net coding gain. Block Turbo Codes (BTC) have a theoretical potential net coding gain of around 10 dB with a redundant overhead of less than 25 % [START_REF] Sab | Block turbo code performances for long-haul dwdm optical transmission systems[END_REF][START_REF] Mizuochi | Recent progress in forward error correction and its interplay with transmission impairments[END_REF]. Typically, realistic block turbo codes can operate at less than 1dB from the Shannon limit for a binary symmetric channel. Very high-speed data transmission developed for fiber optical networking systems have necessitated the implementation of ultra high-speed FEC architectures to meet the continuing demands for even higher data rates. Currently, the RS(255,239) code can be used in ultra high-speed (40 Gb/s [START_REF] Song | 10-and 40-gb/s forward error correction devices for optical communications[END_REF] and 80 Gb/s [START_REF] Lee | A high-speed low-complexity reed-solomon decoder for optical communications[END_REF]) fiber optic systems. However higher coding gain can be reached using turbo product codes. In 2002, a new architecture for turbo decoding product codes was presented [START_REF] Cuevas | New architecture for high data rate turbo decoding of product codes[END_REF]. This architecture can theoretically achieve a throughput of 6.4 Gb/s on an ASIC target, but no concrete realisation were performed. In 2005, Mitsubishi Electric announced the development of the first block turbo decoder for 10 Gb/s optical transmission [START_REF] Tagami | A 3-bit soft-decision ic for powerful forward error correction in 10-gb/s optical communication systems[END_REF]. Since the BTC decoder is framed with a dummy sequence, effective input throughput is 193 Mb/s while the information throughput is 156 Mb/s (taking account of the code rate). In classical parallel architecture approaches [START_REF] Kerouedan | Implementation of a block turbo decoder on a single chip[END_REF], BTC decoders requires a large amount of memory between each half-iteration. In this paper, we show that Interleaving Memory (IM) can be replaced by a simple connection network. In such a parallel architecture, most of the hardware complexity remains in the duplicated elementary Soft Input Soft Output (SISO) decoders. That is the reason why a complexity analysis of the SISO decoder was performed, resulting in a low complexity parallel decoder. This low complexity architecture was finally implemented onto a low cost FPGA device. This paper is organized as follows. Section 2 recalls the basic principles of decoding for product codes: their construction and the turbo decoding process. In Section 3 an innovative, memoryless, full-parallel decoder architecture is presented. In Section 4, we propose a complexity and performance analysis of the elementary decoder which allows a rapid and efficient estimation of the decoder complexity. Section 5 describes an implementation of the resulting turbo decoder within an experimental setup onto an FPGA target.

BTC Coding and Decoding Principles

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

Linear Cyclic Block Codes

Bose Chaudhuri Hocquenghem (BCH) codes are an infinite class of linear cyclic block codes that have capabilities for multiple error detection and correction. Reed-Solomon (RS) codes are a subclass of non-binary BCH codes. Actually, a code is linear if and only if the set of codewords forms a vector subspace over a finite field like a Galois field. Moreover, in a cyclic code, for every codeword c

= (c 0 , c 1 , ..., c n-2 , c n-1 ), c = (c n-1 , c 0 , ..., c n-3 , c n-2
) is also a codeword. Thus all n shifts of c are also codewords. BCH and RS codes are usually specified as BCH(n, k) with binary symbols and RS(n, k) with m-ary symbols. This means that the encoder takes k data symbols and adds (nk) redundant symbols to generate an n symbols codeword. The minimum Hamming distance d is the minimum distance between two distinct codewords, over all pairs of codewords. The decoder can correct up to t symbols that contain errors in a received word, where t = d-1

2 . Concerning BCH codes, it is also possible to extend the code by adding a parity check bit at the end of the codeword. Extended BCH codes are denoted as eBCH codes. This simple overhead allows an increase of the code distance with a factor 1 and the additional complexity is very low.

Algebraic Codes Decoding

Algebraic codes are based on Galois field arithmetic. A (n, k) code works in a Galois field GF(n -1) defined by its generator polynomial. Moreover, given a symbol size m, the maximum codeword length is n = 2 m -1. Decoding algebraic codes consists in resolving the key equation:

S(x)σ (x) = (x)mod(x n-k ).
(1)

S(x)

is the syndrome polynomial, σ (x) is the error locator polynomial and (x) is the error estimator poynomial. First, syndrome values of the to be decoded vector are computed. RS code decoding requires 2t syndromes while BCH codes decoding requires only t syndromes. Then, the roots of the error localisator polynomial is computed, giving the position of the errors. There are many algorithms which efficiently solve this equation. The best known methods are the iterative Berkelamp Massey [START_REF] Berlekamp | Algebraic coding theorie[END_REF][START_REF] Massey | Shift-register synthesis and bch decoding[END_REF] algorithm and the direct Peterson Gorenstein Zierler (PGZ) algorithm [START_REF] Peterson | Encoding and error correcting procedures for the bose chaudhuri codes[END_REF]. Because of its complexity, the PGZ algorithm is mostly used when t < 3, otherwise Berkelamp Massey is mainly employed. Finally, in the case of RS codes, the roots of the error estimator polynomial are computed. It gives the magnitude of the errors. One of the conventionally used algorithms was designed by Forney [START_REF] Forney | On decoding bch codes[END_REF]. In case of BCH codes, the magnitude of the error is always 1. Correction is then obtained by inverting the corrupted bit.

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 = R1 × R2. 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. Figure 1 schematizes the construction of a product code P. In the following sections, we will consider a squared product code, meaning that n 1 = n 2 = n.

D it F it W it R it R' it it α Delay Delay + × + Decoder R it+1 R' it+1
Figure 2 Elementary SISO decoder dedicated to product codes.

Compute extrinsic information

[W] it =[F] it -[R ] it
for each symbol of the DW. 8. Add extrinsic information (multiplied by α it ) to the channel received word,

[R ] it+1 = [R] it + a it [W] it
A α it coefficient allows decoding decisions to be dampened during the first iterations. It should be noted that decoding parameters Lr, Tp, and Cw have a notable effect on decoding performance.

Parallel Decoding

Previous Work

Many block turbo decoder architectures have been 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 such an implementation, memory blocks are necessary between each half-iteration to store [R ] it and [R] it . Each memory block is then composed of four memories of q × n 2 symbols where q is the number of bits to quantize the matrix symbols. This solution presents several drawbacks. First, a large amount of memory is required which increase the global latency of the system. Moreover, increasing the parallelism degree of each half-iteration produces memory conflicts when several data have to be addressed 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 several symbols at the same time. This data organization does not require any particular memory architecture. The results obtained show that the turbo decoding throughput is increased by m 2 when m elementary decoders processing m data simultaneously are used and its latency is divided by m. The area of the m elementary decoders (m-e-dec) is increased by m 2 2 while the memory is constant. A m-e-dec decoder denotes an elementary decoder which decodes m symbols in one clock period. In [START_REF] Chi | High speed vlsi architecture design for block turbo decoder[END_REF], authors suggested to use a barrel shifter between decoding resources and the IM in order to avoid memory conflicts. This solution enables reaching an increased parallelism rate P = n by rotating the to be stored data. The extracomplexity only consists in a barrel shifter with a complexity in O(nlog(n)). However, the IM requirement is still prohibitive. In the next section, we describe a innovative scheduling for block turbo decoding. In the corresponding architecture, the IM is replaced by a simple interconnection network.

Full-parallel Decoding Principle

The codewords of all rows (or all columns) of a matrix are independent. Consequently, they can be decoded in parallel. If the architecture is composed of n elementary decoders for each half-iteration, an appropriate treatment of the matrix enables the elimination of the reconstruction of the matrix between each decoding. Let i and j be the indices of a row and a column of the n 2 matrix. In full-parallel processing, the row decoder i begins the codeword decoding by the symbol in the i th position. Moreover, each row decoder processes the codeword symbols by increasing the index by one modulo n. Similarly, the column decoder j begins the codeword decoding by the symbol in the j th position. In addition, each column decoder processes the codeword symbols by decreasing the index by one modulo n. Therefore, each new decoded data is immediately used by the next half-iteration decoders and data only require to be properly routed. Consequently, no IM is required. The full-parallel decoding of a product code matrix is detailed in Fig. 3. The proposed decoding scheme is presented in the case of a squared product code (n 1 = n 2 = n). The method is also applicable to non-squared codes such as n 1 = n 2 . Defining n min as n min = min(n 1 , n 2 ), it is possible to decode n min rows and n min columns in parallel.

The latency of an elementary decoder depends on the structure of the elementary decoder and the codeword length n. As the reconstruction matrix is removed, the latency between row and column decoding is null. The major advantage of our full-parallel architecture is that it enables the memory block of 4 × q × n symbols between each half-iteration to be removed. However, the codeword symbols exchanged between the row and column decoders have to be scheduled. One solution is to use a connection network for this task. In our case, we have chosen an Omega network. The Omega network is one of several connection networks used in parallel machines [START_REF] Lawrie | Access and alignment of data in an array processor[END_REF]. It is composed of log 2 n stages, each having n 2 exchange elements. In fact, a n-input Omega network contains log 2 n 2 switch transfer blocks and n log 2 n connections. More details about the architecture can be found in Section 7.3. For example, the equivalent gate complexity of a network with 32 inputs quantized with 1 bit can be estimated to be 200 per exchange bit. The proposed full-parallel architecture for product codes is presented in Fig. 4. It is composed of cascaded modules for the block turbo decoder. Each 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. Actually, the full-parallel turbo decoder complexity essentially depends on the complexity of the elementary decoder and the code size n.

The proposed IM-less architecture eliminates the latency due to matrix reconstruction while maximizing the reachable throughput. It also reduces the interleaving resources from a large amount of memory to a simple omega network. The structure and the complexity of an omega network is detailed in Section 7.3. Figure 5 shows the complexity (in equivalent logic gate count) for the previous and proposed architectures. The curve A corresponds to the architecture proposed in [START_REF] Cuevas | New architecture for high data rate turbo decoding of product codes[END_REF], the curve B corresponds to [START_REF] Chi | High speed vlsi architecture design for block turbo decoder[END_REF] and curve C represents the interleaving logic complexity of the proposed architecture. Area estimation were plotted using a memory area estimation model provided by ST-Microelectronics. It clearly shows that the IM architecture drastically reduces the IM requirements, especially when the code size increases.

Considering the proposed interleaving memoryless architecture, the remaining complexity is in the decoding processors. In such a parallel architecture, 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. A SISO decoder complexity can be reduced by a decrease of algorithmic parameters values. However, these simplifications lead to a loss in performance which have to be estimated. In the next section, we propose a method to find a good tradeoff between complexity and decoding performance.

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 = 500 MHz. BER performance was simulated using C-ANSI models of a turbo decoder for the product codes eBCH(16,11) 2 and eBCH(32,26) 2 .

Complexity Analysis of BCH SISO Decoders

A conventional SISO decoder is composed of twelve processing parts (see Fig. 8 in Section 7.2). Running these existing 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 α it multiplication unit. In classical architectures, it is implemented as a conversion table. Input can be multiplied by 0.55 < α it < 0.75, the value depending on the current iteration. Keeping α it = 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 depend on parameters introduced in Section 3.2.

Decoding parameters Lr, Tp, Cw, as well as the code size n and the number of quantization bits q have a direct impact on the decoder complexity (area or number of logical gates). Considering a code size n, let's define a set p i of decoding parameters:

p i = q i , Cw i , Tp i , Lr i .
(

) 2
Table 1 Order of complexity of the three critical parts of a SISO decoder

Blocks n q L r T p C w Dw-Cw Sorting O(n log(n) O(q) O(Lr) O(Tp) O(Cw) Lr sorting O(q) O(Lr) O(Tp) Reliability O(n log(n) O(q) O(Lr) O(Tp) O(Cw) computation
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, Tp 0 = 16, Lr 0 = 5. (3)
It gives the best decoding performance (0.1 dB from the optimal decoding limit). Moreover, increasing parameters values of p 0 does not significantly improve performance. 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:

C pi (n) = (1/3)(C p0 (n)) + C pi (n). ( 4
)
where C pi (n) is the cumulated complexity of the four critical parts in terms of logical gates for a parameter set p i . More details can be found in the Appendix. 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(Tp i -4) + 46(Lr i -2) + 1019 (5)
The model's accuracy was measured a posteriori. The maximum and average errors (between model and synthesis results) are 8% and 2.5% respectively. The total area of a half-iteration is given by:

C T = nC p i (n) + 2C (n, q) + C RAM (n, q), (6)
where C (n, q) is the area of a omega network routing n data of q bits and C RAM (n, q) is the area of the internal memory required in the SISO decoder as explained in Section 7.2.

A Complexity-Performance Tradeoff Case of Study

The previously presented model can be used in order find a good tradeoff between performance and complexity. A case of study was performed for a code eBCH(32,26) 2 . The coding gain at BER = 10 -6 and the complexity of a half-iteration were computed for different parameter sets. Figure 6 shows the impact of decoding parameters on the performance and the complexity.

First, it can be observed that the complexity variation can be significant: C T ( p 6 ) -C T ( p 0 ) = 25Kgates per half-iteration while the corresponding performance loss is 0.8dB. Comparing p 0 , p 3 and p 4 show that, at BER=10 -6 , Cw does not impact the decoding performance while the complexity linearly decreases with Cw. The effect of the quantization q is highlighted by parameter sets p 0 , p 1 and p 2 . The quantization level q has a notable impact on decoding performance and have to be chosen considering the potential performance loss in performance. The same remark can be done for Tp when considering parameter sets p 0 , p 5 and p 6 . This case of study does not have any pretention to generalize the impact of each parameter on decoding performance but it does show some trends of the complexity for the different parameter sets. When coupled with algorithmic performance considerations, such a complexity model can help the designer to efficiently explore the design space of the block turbo decoder.

Towards Prototyping

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 [START_REF]Xilinx university program Virtex-II pro development system[END_REF] development system from Digilent was selected for our experimentation. These boards contain a Xilinx Virtex II-Pro XC2VP30 FPGA device with 13,696 slices. Preliminary syntheses show that only a half-iteration of the eBCH(32,26) 2 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 eBCH(16,11) 2 , up to 3 half-iterations (48 SISO decoders) can be implemented onto the same low-cost Xilinx VII Pro FPGA device. For this reason, the eBCH(16,11) 2 was finally chosen for our experimentation. The main concern of the implementation phase was the limited resources available on the targeted component. The complexity model was transposed for a FPGA target and it provided an estimation of the complexity (slices number instead of gates count) for different parameter sets. Algorithmic simulations showed that for a small size of product code (eBCH [START_REF] Elias | Error-free coding[END_REF][START_REF] Kerouedan | Implementation of a block turbo decoder on a single chip[END_REF] 2 ), the performance degradation associated with the particular set p 7 = Cw = 1, q = 4, Tp = 4, Lr = 2 was reasonnable. Replacing parameter set p 0 by p 7 degrades performance, but the gap is only 0.4 dB at BER=10 -2 while it becomes insignificant (<0.1 dB) at BER=10 -6 . Compared with p 0 , the complexity is reduced by 30% and allows one full-iteration to fit onto the Virtex II Pro.

Full-parallel Encoder and Turbo Decoder

Implementations on an FPGA Device

Full-parallel Encoder Architecture

Linear block codes encoding consists in dividing information vector k by the polynomial generator of the considered code. This is conventionally implemented by a set of shift registers with some feedback logic.

In a conventional product codes encoding process, k 1 rows are firstly encoded using the code C 2 . Therefore, a k 1 × (n 2k 2 ) redundancy block is obtained. Then the n 2 columns composed of k 1 × k 2 information bits and k 1 × (n 2k 2 ) redundancy bits are encoded. This sequential approach requires a k 1 × n 2 memory block between rows and columns encoding. Alternatively, a linear block code can be encoded by multiplying the information vector k by the generator matrix. This can be easily implemented by an XOR arborescence which is a parallel combinatorial solution. The original proposed encoding scheme uses both sequential and parallel encoders. k sequential encoders process k 1 rows and a parallel encoder processes the n 2 columns. Figure 7 shows the three first steps of the encoding process for a [START_REF] Song | 10-and 40-gb/s forward error correction devices for optical communications[END_REF][START_REF] Azadet | Equalization and fec techniques for optical transceivers[END_REF] code. It also depicts the corresponding architecture.

During the first clock period, k 1 sequential encoders process the first bit of the k 1 rows. Next, the sequential encoder processes the second bit of each of the k 1 rows while the parallel encoder processes simultaneously the In the previous approaches, it was necessary to encode all k 1 rows before starting to encode the n 2 columns. A k 1 × n 2 size memory was then required. The depicted architecture decreases the latency from k 1 × n 2 to only 1 symbol and avoids the use of an intermediate k1 × n2 memory block.

E R0 E R1 E R2 E R3 E R0 E R1 E R2 E R3 E C E C E C E C E R0 E R1 E R2 E R3 E C E C E C E C E R0 E C Bit processed

Full-parallel Decoder Architecture

Full-parallel decoder architecture has been detailed in Section 4.3. It was observed that most of the complexity remains in the duplicated SISO decoders. The complex-ity analysis performed in Section 5 allowed us to select a configuration to be implemented on the SISO decoder. The elementary SISO decoder architecture will now be detailed as depicted on Fig. 8.

All the soft information within the decoder is quantized and processed with q = 4 bits (1 sign bit and 3 reliability bits). The SISO decoder architecture is structured in three pipelined stages identified as reception, processing and emission units. Each stage processes n = 16 symbols in n = 16 clock periods. According to the latency definition given in Section 4.2, the resulting latency is then equal to 2n = 32 clock symbols. The reception unit computes the syndrome S 0 and the Lr = 2 least reliable bits of the word received [R ] it . This unit is also in charge of the decoder scheduling by generating A new q-bits symbol is then transmitted at each clock period. The decoding process needs to access the [R] it and [R ] it values during the three decoding phases. For this reason, these words are implemented into Random Access Memories (RAM) of size q × n controlled by a finite state machine.

Q Least Reliable computing Scheduling R' it R it Lr S 0 Tv M i Dw-Cw Dw-Cw sorting R it+1 R' it+1 F it W it it W α it α it R' it+1 R it+1

Omega Network Implementation

The multi-stage dynamically reconfigurable interconnection network omega is based on a circular permutation principle. The connecting scheme consists of circularly shifted input data. Figure 9 shows an example of communication between two sets of 8 SISO decoders. Switches are simple logic elements that have two possible controllable routing configurations. Such switches blocks are easily implementable in CMOS technology. Indeed, a 2-input switch presents an equivalent complexity of 2.5 logical gates. The complexity of an omega network with n inputs and q-bits quantized data is then setup is clocked at f 0 = 37.5 MHz. Figure 10 shows the different components of the communication setup implemented onto the FPGA. At BER = 10 -4 , we have a gap of 0.2 dB. This difference tends to slightly increase with SNR. However, bittrue simulations showed that the turbo decoder strictly performs like the C reference program. Indeed, when providing the same soft inputs to both decoders, soft outputs are exactly the same. Consequently the divergence is most probably due to the Gaussian channel implementation. The same trend was observed using this channel implementation with a simple convolutional SISO decoder which again excludes the decoding fault possibility.

C (n, q) = 2.5 × q × n 2 × log n (7) n control

Characteristic and Performance

Clocked at only 37.5 MHz, the turbo decoder processes input data at 600 Mb/s. This frequency is limited by the communication protocol. The turbo decoder can actually perform up to 50 MHz on this target, which corresponds to 800 Mb/s. Using an FPGA device optimized for high-performance logic would lead to even higher frequency. The output throughput, it is defined as:

T out = P × f × R. ( 8
)
P is the parallelism rate (max(P) = n), f the elementary decoder frequency and R the code rate. In our case, P = 16, f = f 0 = 37.5 MHz and R = 0.473, the resulting throughput is then 284 Mb/s. Several solutions exist to increase the throughput, the most 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 f 0 = 37.5 MHz, the input and output throughput become 1.2 Gb/s and 792 Mb/s respectively. In our architecture, SISO decoders process data sequentially. Designing SISO decoders that decode several data in one clock period, as in [START_REF] Cuevas | New architecture for high data rate turbo decoding of product codes[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 throughput even more.

Conclusion

This article presents an innovative architecture for both encoding and turbo decoding of product codes. After introducing the full-parallel decoding principle, we also show how we implemented this memory free, high-throughput, full-parallel, block turbo decoder on an FPGA device. In such parallel architectures, it is necessary to use low complexity SISO decoders. Thus, we proposed a complexity analysis for the eBCH(n, k) 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 (-30%) to be duplicated in the parallel turbo decoder. Next, we describe the experimental setup designed to test the turbo decoder also including a full-parallel encoder. Using a more efficient communication protocol the turbo decoder can process input data at 3.2 Gb/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. Currently, a study for proposing a BTC implementation on an FPGA device for the physical layer of a 10 Gb/s optical access network is in progress.

Appendix: SISO Complexity Approximation Proof

C pi (n) is the cumulated complexity of the four critical parts in terms of logical gates for a parameter set p i and a code size n.C pi (n) is the SISO decoder complexity in terms of logical gates. Let's first assume that,

C p0 (n) -C p i (n) ≈ C p0 (n) -C p i (n) (9)
(verified during syntheses) Since the 4 critical blocks represent 75% of the complexity, we have

C p0 (n) = ((C p0 (n))/(0.75)) (10)
Combining ( 9) and ( 10), we obtain, Michel Jézéquel (M'02) was born in Saint Renan, France, on February 26, 1960. He received the degree of "Ingénieur" in electronics from the "École Nationale Supérieure de l'Électronique et de ses Applications", Paris, France in 1982. In the period 1983-1986 he was a design engineer at CIT ALCATEL in Lannion, France. Then, after an experience in a small company, he followed a one year course about software design. In 1988, he joined the École Nationale Supérieure des Télécommunications de Bretagne, where he is currently Professor, head of the Electronics Department. His main research interest is circuit design for digital communications. He focuses his activities in the fields of Turbo codes, adaptation of the turbo principle to iterative correction of intersymbol interference, the design of interleavers and the interaction between modulation and error correcting codes.

C p i (n) = (1/3)(C p0 (n)) + C pi (n) ( 11

Figure 1

 1 Figure 1 Structure of a product code matrix.

Figure 3

 3 Figure 3Full-parallel decoding of a product code matrix.

4. 3

 3 Full-parallel Architecture for Product Codes Turbo Decoder

Figure 5

 5 Figure 5 Comparison of internal memory complexity for a half-iteration.

Figure 6 A

 6 Figure 6 A complexity performance tradeoff for the eBCH(32,26) 2 code.

Figure 7

 7 Figure 7 Product code parallel encoding scheme and architecture.

Figure 8

 8 Figure 8 Architecture of a SISO decoder.

  . The processing unit computes the syndrome of the Tp = 4 test patterns and their metric values. It also sequentially selects the decided word and the concurrent ones. The emission unit calculates new reliabilities from metrics of the decided word and the Cw = 1 concurrent word. Extrinsic information [W] k and soft output [R ] it+1 are also processed during the same clock period.

)

  Christophe Jégo was born in Auray, France, in 1973. He received the M.S. and Ph.D. degrees from the Université Rennes 1, Rennes, France, in 1996 and 2000, respectively. He joined the Electronic Engineering Department of TELECOM Bretagne as a full-Time Associate Professor in 2001. He was a visiting professor in the Department of Electrical and Computer Engineering at McGill University during 10 months (Sept. 2006 -June 2007). His research activities are concerned with analysis and design of architectures for iterative processing in the digital communication systems. Patrick Adde was born in Caen, France, in 1953. He received the degree of "Ingénieur" from the "École Nationale d'ingénieur de Brest", Brest, France in 1974. In 1979, he joined the École Nationale Supérieure des Télécommunications de Bretagne, where he is currently Professor. His research interests are about the design of efficiency architectures for turbo decoding of product codes.

  sequences of the omega network are generated by a configuration ROM in n cycles. The ROM is addressed by a modulo n counter. The implemented turbo decoder contains 2n = 32 SISO decoders per iteration and two connection omega networks. Between two half-iterations, two omega network are required to transmit [R ] it+1 and [R] it . The complexity of the implemented 16×16 omega network for 1 iteration is then: 2 × C (16, 8) = 320 logical gates.

						SNR
	Transmitter FPGA								Receiver FPGA
	PRG	11	eBCH(16,11) 2 Parallel Encoder	16	AWGN Channel	64	Aurora Transmission protocol	32	Aurora Reception protocol	64		eBCH(16,11) 2 Parallel Turbo	f 0	PRG 11
															Decoder	11	BER	BER
	f 0		f 0			f 0		f 1				f 1			f 0	Module
	LFSR	1 bit	11 bits	BCH SEQ encoder		16	WGN	4	+	4	64	64	4	decoder SISO	decoder SISO
	LFSR LFSR LFSR			encoder BCH SEQ encoder BCH SEQ encoder BCH SEQ	BCH Parallel Encoder		… WGN	8 Implementation of a Block Turbo Decoder decoder decoder in an Ultra High Rate Communication Setup SISO SISO 1 decoder SISO network SISO network decoder decoder SISO decoder SISO Ω Ω +	11
	LFSR …	1 bit		… encoder BCH SEQ	1		Ö WGN	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. decoder decoder SISO SISO … … +
	Figure 10 Mult-gigabit experimental setup.
									8.1 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 up to 2.4 Gb/s rate.
									Indeed, encoded noisy data are sent from the trans-
									mitter FPGA to the receiver FPGA using the high
									speed Xilinx Aurora protocol. Each board has its own
									digital clock management system operating at 50 MHz.
									Synchronization between the two boards is carried out
									by Aurora protocol control signals. The Aurora pro-
									tocol is clocked at f 1 = 75 MHz and the rest of the
	Figure 9 Architecture of a 8-input network.			Dec L0		Dec C0	Dec L0					log 2 (n) = 3 stages	Dec C0
									Dec L1					Dec C1
						Dec L1		Dec C1	Dec L2					Dec C2
						Dec L2		Dec C2	Dec L3					Dec C3
									Dec L4					Dec C4
					N=8 decoders	Dec L3 Dec L4 Dec L5		Dec C3 Dec C4 Dec C5	Dec L5 Dec L6 Dec L7 counter adr Modulo 8	0111		0011	0000	Dec C5 Dec C6 Dec C7
						Dec L6		Dec C6					Network Configuration ROM
						Dec L7		Dec C7
										1		0

Acknowledgements

The authors would like to thank Gerald Le Mestre for his significant help during the experimental setup design phase.


Raphaël Le Bidan

Camille Leroux

Christophe Jégo

Patrick Adde

Ramesh Pyndiah

Reed-Solomon Turbo Product Codes for Optical Communications: From Code Optimization to Decoder Design

Turbo product codes (TPC) are an attractive solution to improve link budgets and reduce systems costs by relaxing the requirements on expensive optical devices in highcapacity optical transport systems. In this paper, we investigate the use of Reed-Solomon (RS) turbo product codes for 40 Gb/s transmission over optical transport networks and 10 Gb/s transmission over passive optical networks. An algorithmic study is first performed in order to design RS TPCs that are compatible with the performance requirements imposed by the two applications. Then, a novel ultra-high-speed parallel architecture for turbo decoding of product codes is described. A comparison with binary Bose-Chaudhuri-Hocquenghem (BCH) TPCs is performed. The results show that high-rate RS TPCs offer a better complexity/performance trade-off than BCH TPCs for low-cost Gb/s fiber optic communications.

I. INTRODUCTION

The field of channel coding has undergone major advances for the last twenty years. With the invention of turbo codes [START_REF] Berrou | Near shannon limit errorcorrecting coding and decoding: Turbo-Codes[END_REF] followed by the rediscovery of low-density parity-check (LDPC) codes [START_REF] Gallager | Low-density parity-check codes[END_REF], it is now possible to approach the fundamental limit of channel capacity within a few tenths of a decibel over several channel models of practical interest [START_REF] Costello | Channel coding: The road to channel capacity[END_REF]. Although this has been a major step forward, there is still a need for improvement in forward-error correction (FEC), notably in terms of code flexibility, throughput and cost.

In the early 90's, coinciding with the discovery of turbo codes, the deployment of FEC began in optical fiber communication systems. For a long time, there was no real incentive to use channel coding in optical communications since the bit error rate (BER) in lightwave transmission systems can be as low as 10 -9 -10 -15 . In contrast, the typical BER range of wireless communications is several orders of magnitude larger, around 10 -5 . Then, the progressive introduction of inline optical amplifiers and the advent of wavelength division multiplexing (WDM) technology accelerated the use of FEC up to the point that it is now considered almost routine in optical communications. Channel coding is seen as an efficient technique to reduce systems costs and to improve margins against various line impairments such as beat noise, channel cross-talk or non-linear dispersion. On the other hand, the design of channel codes for optical communications poses remarkable challenges to the system engineer. Good codes are This paper was presented in part at IEEE International Conference on Communication, Glasgow, Scotland, in June 2007.The authors are with the GET / ENST Bretagne, CNRS TAMCIC Research Laboratory (UMR 2872) , Technopôle Brest-Iroise, CS 83818, 29238 Brest Cedex 3, France (e-mail: firstname.lastname@enst-bretagne.fr).

indeed expected to provide at the same time low overhead (high code rate) and guaranteed large coding gains at very low BER [START_REF] Benedetto | Channel coding for optical communications[END_REF]. Furthermore, the issue of decoding complexity should not be overlooked since data rates have now reached 10 Gb/s and beyond (up to 40 Gb/s), calling for FEC devices with low power consumption.

FEC schemes for optical communications are commonly classified into three generations. The reader is referred to [START_REF] Mizuochi | Recent progress in forward error correction for optical communication systems[END_REF], [START_REF]Recent progress in forward error correction and its interplay with transmission impairments[END_REF] for an in-depth historical perspective of FEC for optical communication. First-generation FEC schemes mainly relied on the (255, 239) Reed-Solomon (RS) code over GF(256), with only 6.7% overhead, as recommended by the ITU for long-haul submarine transmissions. Then, the development of WDM technology provided the impetus for moving to secondgeneration FEC systems, based on concatenated codes with higher coding gains [START_REF]Forward error correction for high bit rate DWDM submarine systems[END_REF]. Third-generation FEC based on softdecision decoding is now the subject of intense research since stronger FEC are seen as a promising way to reduce costs by relaxing the requirements on expensive optical devices in high-capacity transport systems.

First introduced in [START_REF] Pyndiah | Near optimum decoding of product codes[END_REF], turbo product codes (TPC) based on binary Bose-Chaudhuri-Hocquenghem (BCH) codes is an efficient and mature technology that has found its way in several (either proprietary or public) wireless transmission systems [START_REF] Gracie | Turbo and turbo-like codes: Principles and applications in telecommunications[END_REF]. Recently, BCH TPCs have received considerable attention for third generation FEC in optical systems since they show good performance at high code rates and have a high minimum distance by construction. Furthermore, their regular structure is amenable to very-high-data-rate parallel decoding architectures [START_REF] Cuevas | New architecture for high data rate turbo decoding of product codes[END_REF], [START_REF] Jego | Full-parallel architecture for turbo decoding of product codes[END_REF]. Research on TPCs for lightwave systems culminated recently with the experimental demonstration of a record coding gain of 10.1 dB at a BER of 10 -13 using a (144, 128) × (256, 239) BCH turbo product code with 24.6% overhead [START_REF] Mizuochi | Forward error correction based on block turbo code with 3-bit soft decision for 10-Gb/s optical communication systems[END_REF]. This gain was measured using a turbo decoding very-large-scale-integration (VLSI) circuit operating on 3-bit soft inputs at an information rate of 12.4 Gb/s. LDPC codes are also considered as serious candidate for third generation FEC. Impressive coding gains have notably been demonstrated by Monte-Carlo simulation [START_REF] Djordjevic | Low-density parity-check codes for 40-Gb/s optical transmission systems[END_REF]. To date however, to the best of the authors knowledge, no highrate LDPC decoding architecture has been proposed in order to support the practicality of LDPC codes for Gb/s optical communications.

In this work, we investigate the use of Reed-Solomon TPCs for third generation FEC in fiber optic communication. Two specific applications are envisioned, namely 40 Gb/s line rate transmission over optical transport networks (OTN), and 10 Gb/s data transmission over passive optical networks (PON). These two applications have different requirements with respect to FEC. An algorithmic study is first carried out in order to design RS product codes for the two applications. In particular, it is shown that high-rate RS TPCs based on carefully designed single-error-correcting RS codes realize an excellent performance/complexity trade-off for both scenarios, compared to binary BCH TPCs of similar code rate. In a second step, a novel parallel decoding architecture is introduced. This architecture allows decoding of turbo product codes at data rates of 10 Gb/s and beyond. Complexity estimations show that RS TPCs better trade off area and throughput than BCH TPCs for full-parallel decoding architectures. An experimental setup based on field-programmable gate array (FPGA) devices has been successfully designed for 10 Gb/s data transmission. This prototype demonstrates the practicality of RS TPCs for next-generation optical communications.

The remainder of the paper is organized as follows. Construction and properties of RS product codes are introduced in Section II. Turbo decoding of RS product codes is described in Section III. Product code design for optical communication and related algorithmic issues are discussed in Section IV. The challenging issue of designing high-throughput parallel decoding architecture for product codes is developed in Section V. A comparison of throughput and complexity between decoding architectures for RS and BCH TPCs is carried out in Section VI. Section VII describes the successful realization of a turbo decoder prototype for 10 Gb/s transmission. Conclusions are drawn in Section VIII.

II. REED-SOLOMON PRODUCT CODES

A. Code construction and systematic encoding

Let C 1 and C 2 be linear block codes over the Galois field GF(2 m ), with parameters (N 1 , K 1 , D 1 ) and (N 2 , K 2 , D 2 ), respectively. The product code [START_REF] Macwilliams | The theory of error-correcting codes[END_REF]. The direct product construction thus offers a simple way to build long block codes with relatively large minimum distance using simple, short component codes with small minimum distance. When C 1 and C 2 are two RS codes over GF(2 m ), we obtain an RS product code over GF(2 m ). Similarly, the direct product of two binary BCH codes yields a binary BCH product code.

P = C 1 ⊗ C 2 consists of all N 1 × N 2 matrices such that each column is a codeword in C 1 and each row is a codeword in C 2 . It is well known that P is an (N 1 N 2 , K 1 K 2 ) linear block code with minimum distance D 1 D 2 over GF(2 m )
Starting from a K 1 × K 2 information matrix, systematic encoding of P is easily accomplished by first encoding the K 1 information rows using a systematic encoder for C 2 . Then, the N 2 columns are encoded using a systematic encoder for C 1 , thus resulting in the N 1 × N 2 coded matrix shown in Figure 1.

B. Binary image of RS product codes

Optical communication systems usually employ some form of binary signaling. A binary expansion of the RS product code is then required for transmission. The extension field GF(2 m ) Fig. 1. Codewords of the product code

P = C 1 ⊗ C 2 .
forms a vector space of dimension m over GF [START_REF] Gallager | Low-density parity-check codes[END_REF]. A binary image P b of P is thus obtained by expanding each code symbol into the product code matrix into m bits using some basis B for GF(2 m ). The polynomial basis B = {1, α, . . . , α m-1 } where α is a primitive element of GF(2 m ) is the usual choice, although other basis exist [15, chap. 8]. By construction, P b is a binary linear code with length mN 1 N 2 , dimension mK 1 K 2 and minimum distance d at least as large as the symbol-level minimum distance D = D 1 D 2 [START_REF] Macwilliams | The theory of error-correcting codes[END_REF]Sec. 10.5].

III. TURBO DECODING OF RS PRODUCT CODES

Product codes usually have high dimension which precludes maximum-likelihood (ML) soft-decision decoding. Yet the particular structure of the product code lends itself to an efficient iterative "turbo" decoding algorithm offering closeto-optimum performance at high-enough signal-to-noise ratios (SNRs).

Assume that a binary transmission has taken place over a binary-input channel. Let Y = (y i,j ) denote the matrix of samples delivered by the receiver front-end. The turbo decoder soft input is the channel log-likelihood ratio (LLR) matrix R = (r i,j ), with

r i,j = A ln f 1 (y i,j ) f 0 (y i,j ) (1)
Here A is a suitably chosen constant, and f b (y) denotes the probability of observing the sample y at the channel output given that bit b has been transmitted. Turbo decoding is realized by decoding successively the rows and columns of the channel matrix R using soft-input soft-output (SISO) decoders, and by exchanging reliability information between the decoders until a reliable decision can be made on the transmitted bits.

A. SISO decoding of the component codes

In this work, SISO decoding of the RS component codes is performed at the bit-level using the Chase-Pyndiah algorithm. First introduced in [START_REF] Pyndiah | Near optimum decoding of product codes[END_REF] for binary BCH codes and latter extended to RS codes in [START_REF] Aitsab | Performance of Reed-Solomon block turbo codes[END_REF], the Chase-Pyndiah decoder consists of a soft-input hard-output Chase-2 decoder [START_REF] Chase | A class of algorithms for decoding block codes with channel measurement information[END_REF] augmented by a soft-output computation unit.

Given a soft-input sequence r = (r 1 , . . . , r mN ) corresponding to a row (N = N 2 ) or column (N = N 1 ) of R, the Chase-2 decoder first forms a binary hard-decision sequence y = (y 1 , . . . , y mN ). The reliability of the hard-decision y i on the i-th bit is measured by the magnitude |r i | of the corresponding soft input. Then, N ep error patterns are generated by testing different combinations of 0 and 1 in the L r least reliable bit positions. In general, N ep ≤ 2 Lr with equality if all combinations are considered. Those error patterns are added modulo-2 to the hard-decision sequence y to form candidate sequences. Algebraic decoding of the candidate sequences returns a list with at most N ep distinct candidate codewords. Among them, the codeword d at minimum Euclidean distance from the input sequence r is selected as the final decision.

Soft-output computation is then performed as follows. For a given bit i, the list of candidate codewords is searched for a competing codeword c at minimum Euclidean distance from r and such that c i = d i . If such a codeword exists, then the soft output r i on the i-th bit is given by:

r i = ||r -c|| 2 -||r -d|| 2 4 × d i (2)
where || • || 2 denotes the squared norm of a sequence. Otherwise, the soft output is computed as follows:

r i = r i + β × d i (3)
where β is a positive value, computed on a per-codeword basis, as suggested in [START_REF] Adde | Recent simplifications and improvements in block turbo codes[END_REF]. Following the so-called "turbo principle", the soft input r i is finally subtracted from the soft output r i to obtain the extrinsic information

w i = r i -r i (4)
which will be sent to the next decoder.

B. Iterative decoding of the product code

The block diagram of the turbo decoder at the k-th halfiteration is shown in Figure 2. A half-iteration stands for a row or column decoding step, and one iteration comprises two half-iterations. The input of the SISO decoder at half-iteration k is given by:

R k = R + α k W k (5)
where α k is a scaling factor used to attenuate the influence of extrinsic information during the first iterations, and where W k = (w i,j ) is the extrinsic information matrix delivered by the SISO decoder at the previous half-iteration. The decoder outputs an updated extrinsic information matrix W k+1 , and possibly a matrix D k of hard-decisions. Decoding stops when a given maximum number of iterations has been performed, or when an early-termination condition (stop criterion) is met. The use of a stop criterion can improve the convergence of the iterative decoding process and also reduce the average power consumption of the decoder by decreasing the average number of iterations required to decode a block. An efficient stop criterion taking advantage of the structure of the product codes was proposed in [START_REF] Pyndiah | Iterative decoding of product codes: block turbo codes[END_REF]. Another simple and effective solution is to stop when the hard decisions do not change between two successive half-iterations (i.e. no further corrections are done).

IV. RS PRODUCT CODE DESIGN FOR OPTICAL

COMMUNICATIONS

Two optical communication scenarios have been identified as promising applications for third generation FEC based on RS TPCs: 40 Gb/s data transport over OTN, and 10 Gb/s data transmission over PON. In this section, we first review the own expectations of each application with respect to FEC. Then, we discuss the algorithmic issues that have been encountered and solved in order to design RS TPCs that are compatible with these requirements.

A. FEC design for data transmission over OTN and PON 40 Gb/s transport over OTN calls for both high coding gains and low overhead (< 10%). High coding gains are required in order to insure high data integrity with BER in the range 10 -13 -10 -15 . Low overhead limit optical transmission impairments caused by bandwidth extension. Note that these two requirements usually conflict with each other to some extent. The complexity and power consumption of the decoding circuit is also a important issue. A possible solution, proposed in [START_REF]Recent progress in forward error correction and its interplay with transmission impairments[END_REF], is to multiplex in parallel four powerful FEC devices at 10 Gb/s. However 40 Gb/s low cost line cards are a key to the deployment of 40 Gb/s systems. Furthermore, the cost of line cards is primarily dominated by the electronics and optics operating at the serial line rate. Thus, a single low-cost 40 Gb/s FEC device could compete favorably with the former solution if the loss in coding gain (if any) remains small enough.

For data transmission over PON, channel codes with low cost and low latency (small block size) are preferred to long codes (> 10Kbits) with high coding gain. BER requirements are less stringent than for OTN and are typically of the order of 10 -10 . High coding gains result in increased link budget [START_REF] Briand | Forward error correction in WDM PON using spectrum slicing[END_REF]. On the other hand, decoding complexity should be kept at a minimum in order to reduce the cost of optical network units (ONU) deployed at the end-user side. Channel codes for PON are also expected to be robust against burst errors.

B. Choice of the component codes

On the basis of the above-mentioned requirements, we have chosen to focus on RS product codes with less than 20% overhead. Higher overheads lead to larger signal bandwidth, thereby increasing in return the complexity of electronic and optical components. Since the rate of the product code is the product of the individual rates of the component codes, RS component codes with code rate R ≥ 0.9 are necessary. Such code rates can be obtained by considering multiple-errorcorrecting RS codes over large Galois fields, i.e. GF(256) and beyond. Another solution is to use single-error-correcting (SEC) RS codes over Galois fields of smaller order (32 or 64). The latter solution has been retained in this work since it leads to low-complexity SISO decoders.

First, it is shown in [START_REF] Zhou | Low-complexity high-rate Reed-Solomon block turbo codes[END_REF] that 16 error patterns are sufficient to obtain near-optimum performance with the Chase-Pyndiah algorithm for SEC RS codes. In contrast, more sophisticated SISO decoders are required with multiple-error-correcting RS codes (see for example [START_REF] Sweeney | Iterative soft-decision decoding of linear block codes[END_REF] or [START_REF] Lalam | An improved iterative decoding algorithm for block turbo codes[END_REF]) since the number of error patterns necessary to obtain near-optimum performance with the Chase-Pyndiah algorithm grows exponentially with mt for a t-error-correction RS code over GF(2 m ).

In addition, SEC RS codes admit low-complexity algebraic decoders. This feature further contributes to reducing the complexity of the Chase-Pyndiah algorithm. For multipleerror-correcting RS codes the Berlekamp-Massey algorithm or the Euclidean algorithm are the preferred algebraic decoding methods [START_REF] Blahut | Algebraic codes for data transmission[END_REF]. But they introduce unnecessary overhead computations for SEC codes. Instead, a more simpler decoder is obtained from the direct decoding method devised by Peterson, Gorenstein and Zierler (PGZ decoder) [START_REF] Peterson | Encoding and error-correction procedures for the Bose-Chaudhuri codes[END_REF], [START_REF] Gorenstein | A class of error correcting codes in p m symbols[END_REF]. First, the two syndromes S 1 and S 2 are calculated by evaluating the received polynomial r(x) at the two code roots α b and α b+1 :

S i = r(α b+i-1 ) = N -1 =0 r α (b+i-1) i = 1, 2 (6)
If S 1 = S 2 = 0, r(x) is a valid codeword and decoding stops.

If only one of the two syndromes is zero, a decoding failure is declared. Otherwise, the error locator X is calculated as:

X = S 2 S 1 (7)
from which the error location i is obtained by taking the discrete logarithm of X. The error magnitude E is finally given by:

E = S 1 X b (8)
Hence, apart from the syndrome computation, at most two divisions over GF (2 m ) are required to obtain the error position and value with the PGZ decoder (only one is needed when b = 0). The overall complexity of the PGZ decoder is usually dominated by the initial syndrome computation step. Fortunately, the syndromes need not be fully recomputed at each decoding attempt in the Chase-2 decoder. Rather, they can be updated in a very simple way by taking only into account the bits that are flipped between successive error patterns [START_REF] Hirst | Fast Chase algorithm with an application in turbo decoding[END_REF]. This optimization further alleviates SISO decoding complexity. On the basis of the above arguments, two RS product codes have been selected for the two envisioned applications. The (31, 29) 2 RS product code over GF [START_REF] Le Bidan | Some results on the binary minimum distance of Reed-Solomon codes and block turbo codes[END_REF] has been retained for PON systems since it combines a moderate overhead of 12.5% with a moderate code length of 4805 coded bits. This is only twice the code length of the classical (255, 239) RS code over GF(256). On the other hand, the (63, 61) 2 RS product code over GF(64) has been preferred for OTN, since it has a smaller overhead (6.3%), similar to the one introduced by the standard (255, 239) RS code, and also a larger coding gain, as we shall see later.

C. Performance analysis and code optimization

RS product codes built from SEC RS component codes are very attractive from the decoding complexity point of view. On the other hand, they have low minimum distance D = 3×3 = 9 at the symbol level. Therefore, it is of capital interest to verify that this low minimum distance does not introduce error flares in the code performance curve that would penalize the effective coding gain at low BER. Monte-carlo simulations can be used to evaluate the code performance down to BER of 10 -10 -10 -11 within a reasonable computation time. For lower BER, analytical bounding techniques are required.

In the following, binary on-off keying (OOK) intensity modulation with direct detection over additive white Gaussian noise (AWGN) is assumed. This model was adopted here as a first approximation which simplifies the analysis and also facilitates the comparison with other channel codes. More sophisticated models of optical systems for the purpose of assessing the performance of channel codes are developed in [START_REF] Bosco | Soft decoding in optical systems[END_REF], [START_REF] Cai | On channel models for predicting soft-decision error correction performance in optically amplified systems[END_REF]. Under the previous assumptions, the BER of the RS product code at high SNRs and under ML soft-decision decoding is well approximated by the first term of the Union bound:

BER ≈ d mN 1 N 2 B d 2 erfc Q d 2 (9)
where Q is the input Q-factor (see [29, The knowledge of the quantities d and B d is required in to predict the asymptotic performance of the code in the high Q-factor (low BER) region using [START_REF] Gracie | Turbo and turbo-like codes: Principles and applications in telecommunications[END_REF]. These parameters depend in turn on the basis B used to represent the 2 m -ary symbols as bits, and are usually unknown. Computing the exact binary weight enumerator of RS product codes is indeed a very difficult problem. Even the symbol weight enumerator is hard to find since it is not completely determined by the symbol weight enumerators of the component codes [START_REF] Tolhuizen | More results on the weight enumerator of product codes[END_REF]. An average binary weight enumerator for RS product codes was recently derived in [START_REF] El-Khamy | On the weight enumerator and the maximum likelihood performance of linear product codes[END_REF]. This enumerator is simple to calculate. However simulations are still required to assess the tightness of the bounds for a particular code realization. A computational method that allows the determination of d and A d under certain conditions was recently suggested in [START_REF] Le Bidan | Some results on the binary minimum distance of Reed-Solomon codes and block turbo codes[END_REF]. This method exploits the fact that product codewords with minimum symbol weight D 1 D 2 are readily constructed as the direct product of a minimum-weight row codeword with a minimum-weight column codeword. Specifically, there are exactly

A D1D2 = (2 m -1) N 1 D 1 N 2 D 2 (10)
distinct codewords with symbol weight

D 1 D 2 in the product code C 1 ⊗ C 2 .
They can be enumerated with the help of a computer provided A D1D2 is not too large. Estimates d and This method has been used to obtain the binary minimum distance and multiplicity of the (31, 29) 2 and (63, 61) 2 RS product codes using narrow-sense component codes with generator polynomial g(x) = (x -α)(x -α 2 ). This is the classical definition of SEC RS codes that can be found in most textbooks. The results are given in Table I. We observe that in both cases, we are in the most unfavorable case where the bit-level minimum distance d is equal to the symbol-level minimum distance D, and no greater. Simulation results for the two RS TPCs after 8 decoding iterations are shown in Figures 3 and4, respectively. The corresponding asymptotic performance calculated using [START_REF] Gracie | Turbo and turbo-like codes: Principles and applications in telecommunications[END_REF] are plotted in dashed lines. For comparison purpose, we have also included the performance of algebraic decoding of RS codes of similar code rate over GF(256). We observe that the low minimum distance introduces error flares at BER of 10 -8 and 10 -9 for the (31, 29) 2 and (63, 61) 2 product codes, respectively. Clearly, the two RS TPCs do not match the BER requirements imposed by the envisioned applications.

One solution to increase the minimum distance of the product code is to resort to code extension or expurgation. However this approach increases the overhead. It also increases decoding complexity since a higher number of error patterns is then required to maintain near-optimum performance with the Chase-Pyndiah algorithm [START_REF] Zhou | Low-complexity high-rate Reed-Solomon block turbo codes[END_REF]. In this work, another approach has been considered. Specifically, investigations have been conducted in order to identify code constructions that can be mapped into binary images with minimum distance larger than 9. One solution is to investigate different basis B. How to find a basis that maps a non-binary code into a binary code with bit-level minimum distance strictly larger than the symbol-level designed distance remains a challenging research problem. Thus the problem was relaxed by fixing the basis to be the polynomial basis, and studying instead the influence of the choice of the code roots on the minimum distance of the binary image. Any SEC RS code over GF(2 m ) can be compactly described by its generator polynomial

g(x) = (x -α b )(x -α b+1 ) ( 11
)
where b is an integer in the range 0 . . . 2 m -2. Narrow- I. Interestingly, the alternate product codes have a minimum distance d as high as 14 at the bit-level, at the expense of an increase of the error coefficient B d . Thus, we get most of the gain offered by extended or expurgated codes (for which d = 16, as verified by computer search) but without reducing the code rate. It is also worth noting that this extra coding gain is obtained without increasing decoding complexity. The same SISO decoder is used for both narrow-sense and alternate SEC RS codes. In fact, the only modifications occur in the equations ( 6)-( 8) of the PGZ decoder, which actually simplify when b = 0. Simulated performance and asymptotic bounds for the alternate RS product codes are shown in Figures 3 and4. A notable improvement is observed in comparison with the performance of the narrow-sense product codes since the error flare is pushed down by several decades in both cases. By extrapolating the simulation results, the net coding gain (as defined in [START_REF] Mizuochi | Recent progress in forward error correction for optical communication systems[END_REF]) at a BER of 10 -13 is estimated to be around 8.7 dB and 8.9 dB for the RS(31, 29) 2 and RS(63, 61) 2 , respectively. As a result, the two selected RS product codes are now fully compatible with the performance requirements imposed by the respective envisioned applications. More importantly, this achievement has been obtained at no cost.

D. Comparison with BCH product codes

A comparison with BCH product codes is in order since BCH product codes have already found application in optical communications. A major limitation of BCH product codes is that very large block lengths (> 60000 coded bits) are required to achieve high code rates (R > 0.9). On the other hand, RS product can achieve the same code rate than BCH product code, but with a block size about 3 times smaller [START_REF] Zhou | Low-complexity high-rate Reed-Solomon block turbo codes[END_REF]. This is an interesting advantage since, as shown latter in the paper, large block lengths increase the decoding latency and also the memory complexity in the decoder architecture. RS product codes are also expected to be more robust to error bursts than BCH product codes. Both coding schemes inherit burstcorrection properties from the row-column interleaving in the direct product construction. But RS product codes also benefit from the fact that, in the most favorable case, m consecutive erroneous bits may cause a single symbol error in the received word.

A performance comparison has been carried out between the two selected RS product codes and extended BCH (eBCH) product codes of similar code rate: the eBCH(128, 120) 2 and the eBCH(256, 247) 2 . Code extension has been used for BCH codes since it increases minimum distance without increasing decoding complexity nor decreasing significantly the code rate, in contrast to RS codes. Both eBCH TPCs have minimum distance 16 with multiplicities 85344 2 and 690880 2 , respectively. Simulation results after 8 iterations are shown in Figures 3 and4. The corresponding asymptotic bounds are plotted in dashed lines. We observe that eBCH TPCs converge at lower Q-factors. As a result, a 0.3-dB gain is obtained at BER in the range 10 -8 -10 -10 . However, the large multiplicities of eBCH TPCs introduce a change of slope in the performance curves at lower BER. In fact, examination of the asymptotic bounds shows that alternate RS TPCs are expected to perform at least as well as eBCH TPCs in the BER range of interest for optical communication, e.g. 10 -10 -10 -15 . Therefore we conclude that RS TPCs compare favorably with eBCH TPCs in terms of performance. We shall see in the next sections that RS TPCs have additional advantages in terms of decoding complexity and throughput for the target applications.

E. Soft-input quantization

The previous performance study assumed unquantized soft values. In a practical receiver, a finite number q of bits (sign bit included) is used to represent soft information. Soft-input quantization is performed by an analog-to-digital converter (ADC) in the receiver front-end. The very high bit rate in fiber optical systems makes ADC a challenging issue. It therefore necessary to study the impact of soft-input quantization on the performance. Figure 5 presents simulation results for the (63, 61) 2 alternate RS product code using q = 3 and q = 4 quantization bits, respectively. For comparison purpose, the performance without quantization is also shown. Using q = 4 bits yields virtually no degradation with respect to ideal (infinite) quantization, whereas q = 3 bits of quantization introduce a 0.5-dB penalty. Similar conclusions have been obtained with the (31, 29) 2 RS product code and also with various eBCH TPCs, as reported in [START_REF] Bosco | Soft decoding in optical systems[END_REF], [START_REF] Adde | Block turbo code with binary input for improving quality of service[END_REF] for example.

V. FULL-PARALLEL TURBO DECODING ARCHITECTURE DEDICATED TO PRODUCT CODES

Designing turbo decoding architectures compatible with the very high line rate requirements imposed by fiber optics systems at reasonable cost is a challenging issue. Parallel decoding architectures are the only solution to achieve data rates above 10 Gb/s. A simple architectural solution is to duplicate the elementary decoders in order to achieve the given throughput. This results in a turbo decoder with unacceptable cumulative area. Thus, smarter parallel decoding architectures have to be designed in order to better trade off performance and complexity under the constraint of a high-throughput. In the following, we focus on an (N 2 , K 2 ) product code obtained from with two identical (N, K) component codes over GF (2 m ). For 2 m -ary RS codes, m > 1 whereas m = 1 for binary BCH codes.

A. Previous work

Many turbo decoder architectures for product codes have been previously designed. The classical approach involves decoding all the rows or all the columns of a matrix before the next half-iteration. When an application requires highspeed decoders, an architectural solution is to cascade SISO elementary decoders for each half-iteration. In this case, memory blocks are necessary between each half-iteration to store channel data and extrinsic information. Each memory block is composed of four memories of mN 2 soft values. Thus, duplicating a SISO elementary decoder results in duplicating the memory block which is very costly in terms of silicon area. In 2002, a new architecture for turbo decoding product codes was proposed [START_REF] Cuevas | New architecture for high data rate turbo decoding of product codes[END_REF]. The idea is to store several data at the same address and to perform semi-parallel decoding to increase the data rate. However, it is necessary to process these data by row and by column. Let us consider l adjacent rows and l adjacent columns of the initial matrix. The l 2 data constitute a word of the new matrix that has l 2 times fewer addresses. This data organization does not require any particular memory architecture. The results obtained show that the turbo decoding throughput is increased by l 2 when l elementary decoders processing l data simultaneously are used. Turbo decoding latency is divided by l. The area of the l elementary decoders is increased by l/2 while the memory is kept constant.

B. Full-parallel decoding principle

All rows (or all columns) of a matrix can be decoded in parallel. If the architecture is composed of 2N elementary decoders, an appropriate treatment of the matrix allows the elimination of the reconstruction of the matrix between each decoding. Specifically, let i and j be the indices of a row and a column of the N 2 matrix. In full-parallel processing, the row decoder i begins the decoding by the soft value in the i th position. Moreover, each row decoder processes the soft values by increasing the index by one modulo N . Similarly, the column decoder j begins the decoding by the soft value in the j th position. In addition, each column decoder processes the soft values by decreasing the index by one modulo N . Actually, the full-parallel decoding of turbo product code is possible thanks to the cyclic property of BCH and RS codes.

Indeed, every cyclic shift c = (c N -1 , c 0 , ., c N -3 , c N -2 ) of a codeword c = (c 0 , c 1 , ., c N -2 , c N -1
) is also a valid codeword in a cyclic code. Therefore, only one clock period is necessary between two successive matrix decoding operations. The fullparallel decoding of a product code matrix N 2 is detailed in Figure 6. A similar strategy was previously presented in [START_REF] Zhipei | High speed vlsi architecture design for block turbo decoder[END_REF] where memory access conflicts are resolved by means of an appropriate treatment of the matrix.

The elementary decoder latency depends on the structure of the decoder (i.e. number of pipeline stages) and the code length N . Here, as the reconstruction matrix is removed, the latency between row and column decoding is null.

C. Full-parallel architecture for product codes

The major advantage of our full-parallel architecture is that it enables the memory block of 4mN 2 soft values between Fig. 6. Full-parallel decoding of a product code matrix. each half-iteration to be removed. However, the codeword soft values exchanged between the row and column decoders have to be routed. One solution is to use a connection network for this task. In our case, we have chosen an Omega network. The Omega network is one of several connection networks used in parallel machines [START_REF] Lawrie | Access and alignment of data in an array processor[END_REF]. It is composed of log 2 N stages, each having N/2 exchange elements. In fact, the Omega network complexity in terms of number of connections and of 2 × 2 switch transfer blocks is N × log 2 N and N 2 log 2 N , respectively. For example, the equivalent gate complexity of a 31 × 31 network can be estimated to be 200 gates per exchange bit. Figure 7 depicts a full-parallel architecture for the turbo decoding of product codes. It is composed of cascaded modules for the turbo decoder. Each module is dedicated to one iteration. However, it is possible to process several iterations by the same module. In our approach, 2N elementary decoders and 2 connection blocks are necessary for one module. A connection block is composed of 2 Omega networks exchanging the R and R k soft values. Since the Omega network has low complexity, the full-parallel turbo decoder complexity essentially depends on the complexity of the elementary decoder.

D. Elementary SISO decoder architecture

The block diagram of an elementary SISO decoder is shown in Figure 2, where k stands for the current half-iteration number. R k is the soft-input matrix computed from the previous half-iteration whereas R denotes the initial matrix delivered by the receiver front-end (R k =R for the 1 st half-iteration).

W k is the extrinsic information matrix. α k is a constant that depends on the current half-iteration and is used to weight the influence of the extrinsic information during the first iterations. The decoder architecture is structured in three pipelined stages identified as reception, processing and transmission units [START_REF] Kerouedan | Implementation of a block turbo decoder on a single chip[END_REF]. During each stage, the N soft values of the received word R k are processed sequentially in N clock periods. The reception stage computes the initial syndromes S i and finds the L r least reliable bits in the received word. The main function of the processing stage is to build and then to correct the N ep error patterns obtained from the initial syndrome and to combine the least reliable bits. Moreover, the processing stage also has to produce a metric (Euclidean distance between error pattern and received word) for each error pattern. Finally, a selection function identifies the maximum likelihood codeword d and the competing codewords c (if any). The transmission stage performs different functions: computing the reliability for each binary soft value, computing the extrinsic information and correcting of the received soft values. The N soft values of the codeword are thus corrected sequentially. The decoding process needs to access the R and R k soft values during the three decoding phases. For this reason, these words are implemented in six Random Access Memories (RAM) of size q × m × N controlled by a finite state machine. In order to implement of a full-parallel TPC decoder, low-complexity decoders are required.

VI. COMPLEXITY AND THROUGHPUT ANALYSIS OF THE FULL-PARALLEL REED-SOLOMON TURBO DECODERS

Increasing the throughput regardless of the turbo decoder complexity is not relevant. In order to compare the throughput and complexity of RS and BCH turbo decoders, we propose to measure the efficiency η of a parallel architecture by the ratio

η = T C ( 12
)
where T is the throughput and C is the complexity of the design. An efficient architecture will have a high η ratio, that is a high throughput with low hardware complexity. In this Section, we determine and compare the respective efficiency of BCH and RS turbo decoders.

A. Turbo decoder complexity analysis

A turbo decoder of product code corresponds to the cumulative area of computation resources, memory resources and communication resources. In a full-parallel turbo decoder, the main part of the complexity is composed of memory and computation resources. Indeed, the major advantage of our full-parallel architecture is that it enables the memory blocks between each half-iteration to be replaced by Omega connection networks. Communication resources thus represent less than 1% of the total area of the turbo decoder. Consequently, the following study with only focus on memory and computation resources. 1) Complexity analysis of computation resources: The computation resources of an elementary decoder are split into three pipelined stages. The reception and transmission stages have O(log(N )) complexity. For these two stages, replacing a BCH code by an RS code of same code length N (at the symbol level) over GF (2 m ) results in an increase of both complexity and throughput by a factor m. As a result, efficiency is constant in these parts of the decoder. However, the processing stage has a hardware complexity in O(N ep ) error patterns. Consequently, the increase in the local parallelism rate has no influence on the area of this stage and thus increases the efficiency of a RS SISO decoder. In order to verify those general considerations, turbo decoders for the (15, 13) 2 , (31, 29) 2 and (63, 61) 2 RS product codes were described in HDL language and synthesized. Logic syntheses were performed using the Synopsys tool Design Compiler with a ST-microelectronics 90nm CMOS process. All designs were clocked with 100MHz. Moreover, the complexity of BCH turbo decoders were estimated thanks to a complexity model which can derive an estimation of the gate count for any code size and any decoding parameter set. Therefore, taking into account the implementation and performances constraints, this model enables to select a code size N and a set of decoding parameters [START_REF] Leroux | Towards Gb/s turbo decoding of product code onto an FPGA device[END_REF]. In particular, the numbers of error patterns N ep and also the number of competing codewords kept for soft-output computation directly affect both the hardware complexity and the decoding performance. Increasing these parameter values improves performance but also increases complexity.

Table II summarizes some computation resource complexities in terms of gate count for different BCH and RS product codes. Firstly, the complexity of an elementary decoder for each product code is given. The results clearly show that RS elementary decoders are more complex than BCH elementary decoders over the same Galois field. Complexity results for a full-parallel module of the turbo decoding process are also given in Table II. As described in Figure 7, a fullparallel module is composed of 2N elementary decoders and 2 connection blocks for one iteration. In this case, fullparallel modules composed of RS elementary decoders are seen to be less complex than full-parallel modules composed of BCH elementary decoders when comparing eBCH and RS product codes of similar code rate R. For instance, for a code rate R = 0.88, the computation resource complexity in terms of gate count are about 892, 672 and 267, 220 for the BCH(128, 120) 2 and RS(31, 29) 2 , respectively. This is due to the fact that RS codes need smaller code length N (at the symbol level) to achieve a given code rate, in contrast to binary BCH codes. Considering again the previous example, only 31 × 2 decoders are necessary in the RS case for full-parallel decoding compared to 128 × 2 decoders in the BCH case. Similarly, Figure 8 gives computation resource area of BCH and RS turbo decoders for 1 iteration and different parallelism degrees. We verify that higher P (i.e. higher throughput) can be obtained with less computation resources using RS turbo decoders. This means that RS product codes are more efficient in terms of computation resources for full-parallel architectures dedicated to turbo decoding.

2) Complexity analysis of memory resources: A halfiteration of a parallel turbo decoder contains N banks of q × m × N bits. The internal memory complexity of a parallel decoder for one half-iteration can be approximated by

S RAM γ × q × m × N 2 ( 13
)
where γ is a technological parameter specifying the number of equivalent gate counts per memory bit, q is the number of quantization bits for the soft values, and m is the number of bits per Galois field element. Using equation [START_REF] Chase | A class of algorithms for decoding block codes with channel measurement information[END_REF], it can also be expressed as

S RAM = γ × P 2 m × q ( 14
)
where P is the parallelism degree and corresponds to the number of generated bits per clock period (t 0 ). Let us consider a BCH code and an RS code of similar code length N = 2 m -1. For BCH codes a symbol corresponds to 1 bit, whereas it is made of m bits for RS codes. Calculating the SISO memory area for both BCH and RS gives the following ratio:

S RAM (BCH) S RAM (RS) = m = log 2 (N + 1) (15)
This result shows that RS turbo decoders have lower memory complexity for a given parallelism rate. This was confirmed by memory area estimations results showed in Figure 9.

Random access memory (RAM) area of BCH and RS turbo decoders for a half-iteration and different parallelism degrees are plotted using a memory area estimation model provided by ST-Microelectronics. We can observe that higher P (i.e. higher throughput) can be obtained with less memory when using an RS turbo decoder. Thus, full-parallel decoding of RS codes is more memory-efficient than BCH code turbo decoding.

B. Turbo decoder throughput analysis

In order to maximize the data rate, decoding resources are assigned for each decoding iteration. The throughput of a turbo decoder can be defined as

T = P × R × f 0 ( 16
)
where 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 larger 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 can be expressed as

P = N × m (17)
Therefore, enhanced parallelism degree can be obtained by using non-binary codes (e.g. RS codes) with larger code length N . • 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 stages within each elementary SISO decoder. RS and BCH turbo decoders of equivalent code size have equivalent working frequency f 0 since RS decoding is performed by introducing some local parallelism at the soft value level. This result was verified during logic syntheses. The main drawback of pipelining elementary decoders is the extracomplexity generated by internal memory requirement. Since RS codes have higher P and R for equivalent f 0 , RS turbo decoder can reach a higher data rate than equivalent BCH turbo decoder. However, the increase in throughput can not be considered regardless of the turbo decoder complexity.

C. Turbo product code comparison: throughput versus complexity

The efficiency η between the decoder throughput and the decoder complexity can be used to compare eBCH and RS turbo product codes. Table III summarizes the code rate R, the parallelism rate P , the throughput T (Gb/s), the complexity C (kgate) and the efficiency η (kb/s/gate) for each code. We have chosen to clock all designs with f 0 = 100MHz for the computation of the throughput T . An average ratio of 3.5 between RS and BCH decoder efficiency is observed. The good compromise between performance, throughput and complexity clearly makes RS product codes good candidates for next-generation PON and OTN. In particular, the (31, 29) 2 RS product code is compatible with the 10 Gb/s line rate envisioned for PON evolutions. Similarly, the (63, 61) 2 RS product code can be used for data transport over OTN at 40 Gb/s provided the turbo decoder is clocked at a frequency sightly higher than 100MHz.

VII. IMPLEMENTATION OF AN RS TURBO DECODER FOR ULTRA HIGH THROUGHPUT COMMUNICATION

An experimental setup based on FPGA devices has been designed in order to show that RS TPCs can effectively be used in the physical layer of 10 Gb/s optical access networks. Based on the previous analysis, the (31, 29) 2 RS TPC was selected since it offers the best compromise between performance and complexity for this kind of application.

A. 10 Gb/s experimental setup

The experimental setup is composed of a board that includes 6 Xilinx Virtex-5 LX330 FPGAs [38]. A Xilinx Virtex-5 LX330 FPGA contains 51,840 slices that can emulate up to 12 million gates of logic. It should be noted that Virtex-5 slices are organized differently from previous generations. Each Virtex-5 slice contains four Look Up Tables (LUTs) and four flip-flops instead of two LUTs and two flip-flops in previous generation devices. The board is hosted on a 64bit, 66MHz PCI bus that enables communication at full PCI bandwidth with a computer. An FPGA embedded memory block containing 10 encoded and noisy product code matrices is used to generate input data towards the turbo decoder. This memory block exchanges data with a computer thanks to the PCI bus.

One decoding iteration was implemented on each FPGA resulting in a 6 full-iteration turbo decoder as shown in Figure 10. Each decoding module corresponds to a full-parallel architecture dedicated to the decoding of a matrix of 31 × 31 coded soft values. We recall here that a coded soft values over GF [START_REF] Le Bidan | Some results on the binary minimum distance of Reed-Solomon codes and block turbo codes[END_REF] is mapped onto 5 LLR values, each LLR being quantized on 5 bits. Besides, the decoding process needs to access the 31 R and 31 R k 2 m -ary elements during the three decoding phases of a half-iteration as explained in section IV. For theses reasons, 31 × 5 × 5 × 2 = 1, 550 bits have to be exchanged between the decoding modules during each clock period f 0 =65MHz. The board offers 200 chip to chip LVDS for each FPGA to FPGA interconnect. Unfortunately, this number of LVDS is insufficient to enable the transmission of all the bits between the decoding modules. To solve this implementation constraint, we have chosen to add SERializer/DESerializer (SERDES) modules for the parallel-to-serial conversions and for the serial-to-parallel conversions in each FPGA. Indeed, SERDES is a pair of functional blocks commonly used in high speed communications to convert data between parallel data and serial interfaces in each direction. SERDES modules are clocked with f 1 = 2 × f 0 = 130MHz and operate at 8:1 serialization or 1:8 deserialization. In this way, all data can be exchanged between the different decoding modules. Finally, the total occupation rate of the FPGA that contains the more complex design (decoding module + two SERDES modules + memory block + PCI protocol module) is slightly higher than 66%. This corresponds to 34,215 Virtex-5 slices. Note that the decoding module represents only 37% of the total design complexity. More details about this are given in the next section.

Currently, a new design phase of the experimental setup is in progress. The objective is to include channel emulator and BER measurement facilities in order to verify decoding performance of the turbo decoder by plotting some BER curves as in our previous experimental setup [START_REF] Leroux | Towards Gb/s turbo decoding of product code onto an FPGA device[END_REF].

B. Characteristic and performance of the implemented decoding module

A decoding module for one iteration is composed of 31 × 2 = 62 elementary decoders and 2 connection blocks. Each elementary decoder uses information quantized on 5 bits with N ep = 8 error patterns and only 1 competing codeword. These reduced parameter values allow a decrease in the required area for a performance degradation which remains inferior to 0.5dB. Thus a (31, 29) RS elementary decoder occupies 729 slice LUTs, 472 slice Flip-Flops and 3 BlockRAM of 18Kbs. A connection block occupies only 2,325 slice LUTs. Computation resources of a decoding module take up 29,295 slice Flip-Flops and 49,848 slice LUTs. It means that the occupation rates are about 14% and 24% of a Xilinx Virtex-5 LX330 FPGA for slice registers and slice LUTs respectively. Besides, memory resources for the decoding module take up 186 BlockRAM of 18kbits. It represents 32% of the total BlockRAM available in the Xilinx Virtex-5 LX330 FPGA. Note that one BlockRAM of 18kbits is allocated by the Xilinx tool ISE to memorize only 31×5×5 = 775 bits in our design. The occupation rate of each BlockRAM of 18kbits is then only about 4%. As input data are clocked with f 0 =65MHz resulting in an input data rate of T in =10Gb/s. However, taking into account the code rate R=0.87, the output data rate becomes T out =8.7Gb/s. In conclusion, the implementation results showed that a turbo decoder dedicated to the (31, 29) 2 RS product code can effectively be integrated to the physical layer of a 10Gb/s optical access network. A similar prototype with a (63, 61) 2 RS product can be designed for 40 Gb/s transmission over OTN. Indeed, the architecture of one decoding iteration is the same for the two RS TPCs considered in this work. For the (63, 61) 2 RS product code, a decoding module for one iteration is now composed of 63 × 2 = 126 elementary decoders and 2 connection blocks. Logic Syntheses were performed using the Xilinx tool ISE to estimate the complexity of a (63,61) RS elementary decoder. This decoder occupies 1070 slice LUTs, 660 slice Flip-Flops and 3 BlockRAM of 18Kbs. These estimations immediately give the complexity of a decoding module dedicated to one iteration. Computation resources of a (63, 61) 2 RS decoding module take up 83,160 slice Flip-Flops and 134,820 slice LUTs. The occupation rates are then about 40% and 65% of a Xilinx Virtex-5 LX330 FPGA for slice registers and slice LUTs respectively. Memory resources of a (63, 61) 2 RS decoding module take up 378 BlockRAM of 18kbits that represents 65% of the total BlockRAM available in the considered FPGA device. One BlockRAM of 18kbits is allocated by the Xilinx tool ISE to memorize only 63 × 6 × 5 = 1890 bits. For a (63, 61) RS elementary decoder, the occupation rate of each BlockRAM of 18kbits is only about 10.5%.

VIII. CONCLUSION

We have investigated the use of RS product codes for forward-error correction in high-capacity fiber optic transport systems. A complete study considering all the aspects of the problem from code optimization to turbo product code implementation has been performed. Two specific applications were envisioned: 40 Gb/s line rate transmission over OTN and 10 Gb/s data transmission over PON. Algorithmic issues have been ordered and solved in order to design RS turbo product codes that are compatible with the respective requirements of the two transmission scenarios. A novel full-parallel turbo decoding architecture has been introduced. This architecture allows decoding of TPCs at data rates of 10 Gb/s and beyond. In addition, a comparative study has been carried out between eBCH and RS TPCs in the context of optical communications. The results have shown that high-rate RS TPCs offer similar performance at reduced hardware complexity. Finally, we have described the successful realization of a RS turbo decoder prototype for 10 Gb/s data transmission. This experimental setup demonstrates the practicality and also the benefits offered by RS TPCs in lightwave systems. Although only fiber optic systems have been considered in this work, RS TPCs could also find applications in next-generation free-space optical communication.

Fig. 2 .

 2 Fig. 2. Block diagram of the turbo-decoder at the k-th half-iteration.

  chap. 5]), d is the minimum distance of the binary image P b of the product code, and B d the corresponding multiplicity (number of codewords with minimum Hamming weight d in P b ). This expression shows that the asymptotic performance of the product code is determined by the bit-level minimum distance d of the product code, not by the symbol minimum distance D 1 D 2 .

B

  d are then obtained by computing the Hamming weight of the binary expansion of those codewords. Necessarily, d ≤ d. If it can be shown that product codewords of symbol weight > D 1 D 2 necessarily have binary minimum distance > d at the bit level (this is not always the case, depending on the value of d), then it follows that d = d and B d = B d.

Fig. 3 .

 3 Fig. 3. BER performance of the (31, 29) 2 RS product code as a function of the first code root α b , after 8 iterations.

Fig. 4 .

 4 Fig. 4. BER performance of the (63, 61) 2 RS product code as a function of the first code root α b , after 8 decoding iterations.

Fig. 5 .

 5 Fig.5. BER performance for the (63, 61) 2 RS product code as a function of the number of quantization bits for the soft-input (sign bit included).

Fig. 7 .

 7 Fig. 7. Full-parallel architecture for decoding of product codes.

Fig. 8 .

 8 Fig. 8. Comparison of computation resource complexity.

Fig. 9 .

 9 Fig. 9. Comparison of internal RAM complexity.

Fig. 10 .

 10 Fig. 10. 10Gb/s experimental setup for turbo decoding of (31, 29) 2 RS product code

TABLE I MINIMUM

 I DISTANCE d AND MULTIPLICITY B d FOR THE BINARY IMAGE OF THE (31, 29) 2 AND (63, 61) 2 RS PRODUCT CODES AS A FUNCTION OF THE FIRST CODE ROOT α b .

	Product code	mK 2	mN 2	R	b	d	B d
	(31, 29, 3) 2	4205	4805	0.875 1	9	217,186
					0 14	6,465,608
	(63, 61, 3) 2	22326 23814 0.937 1	9	4,207,140
					0 14 88,611,894

ACKNOWLEDGMENTS

The authors wish to acknowledge the financial support of France Telecom R&D. They also thank Gérald Le Mestre for his significant help during the experimental setup design phase.