Implementation results and comparisons
Link to this chapter Copy to clipboard
Cite this chapter Copy to clipboard
Embed this chapter on your site Copy to clipboard
Embed this code snippet in the HTML of your website to show this chapter
Open access peer-reviewed chapter
By Bo Yuan, Li Li and Zhongfeng Wang
Submitted: November 18th 2011Reviewed: May 7th 2012Published: October 3rd 2012
Due to the fast development of Internet, the traffic load of data network has increased dramatically in past decades. Accordingly, optical network, as the major carrier for data transmission, needs to increase its capacity to meet the increasing data rate requirement. As stated in the white paper of Optical Internetworking Forum (OIF) (see ), the rapid growth of data flow demands optical network to double its capacity every 12-18 months. As a result, this critical requirement pushes various types of optical transmission systems to improve their delivered data rate at the same time.
Generally, in high-speed optical communication, the increase on data rate usually comes with the increase on signal bandwidth and sampling rate. In this case, due to the sensitiveness of optical and electronic devices, the additive transmission noise will inevitably increase as well. Therefore, how to increase the throughput of optical network without loss of robustness is an essential task when designing modern high-speed optical network.
To date, various techniques have been employed to enhance the quality of data transmission in optical network. Among those approaches, Forward error correction (FEC), or commonly called error correction coding (ECC), is viewed as the most cost-effective solution, and has been widely adopted in many industrial optical transmission systems. Many specific FEC codes, including Reed-Solomon (RS), BCH, and LDPC codes, are proposed in different industrial standards for error correction in physical layer. Among them, RS code is the earliest and most widely used FEC code in optical communication. For example, RS (255, 239) was the first generation FEC code for submarine fiber-optical transmission in , and its code rate is still the standard parameter for frame design. In addition, for Ethernet network such as 10GBase-LR in , Reed-Solomon (255, 239) code is also the standard FEC code.
There are several reasons for the wide application of RS code. First, modern long-distance optical network, especially long-haul network, is very high-speed system (10Gbps and beyond). For other promising FEC codes, such as LDPC or Turbo code, the corresponding decoding throughput usually can not meet such stringent requirement on data rate, or with the penalty of very high hardware complexity. Instead, RS decoder can achieve such high throughput with affordable hardware resource. Second, for local optical network, such as Ethernet network, the real-time response is an important metric for system design. Compared with its counterpart, RS code has the particular advantage on low decoding latency. Therefore, RS codes are widely employed in modern optical transmission system and are believed to play an important role in next generation optical networks.
Considering the importance of RS code, its efficient implementation is quite important for the optical transmission system. A low-complexity high-speed RS encoding/decoding system will improve the overall performance significantly. Particularly, since RS decoding is the most complex procedure in the RS-based FEC system, efficient RS decoder design should be well-studied. Therefore, targeted to different level of optical communication ranging from short-distance Ethernet network to long-haul backbone system, this chapter fully introduces efficient VLSI design of RS decoder. In addition, to meet the requirement of 100Gbps era, this chapter also discusses some new FEC schemes for ultra high-speed application (beyond 100Gbps).
The chapter is organized as follows. Section 2 reviews the RS decoding. The low-complexity high-speed RS decoders for short-distance network are discussed in Section 3. Section 4 analyzes performance-improved RS burst-error decoder for medium-distance system. Some recent FEC schemes targeted to 100Gbps long-haul network are introduced in Section 5. Section 6 draws the conclusion.
According to the coding theory in , the procedure for decoding RS code contains three main steps: syndrome computation (SC), key equation solving (KES) and Chien search & error evaluation (CSEE). Therefore, the decoding procedure of RS code is summarized as below:
Step 1. (Syndrome computation): For an (n, k) RS code defined over GF(2m) whose primitive element is α in reference , let C(x) and R(x) be the transmitted and received codeword polynomial respectively, and then assumes R(x) = C(x) + E(x), where E(x) is the error polynomial which reflects the errors induced by transmission channel noise. Then, the syndrome polynomial S(x) is computed as follows:
The architecture of SC block of an example RS (255, 239) decoder is shown in Fig. 1. Here R(x)=rn-1xn-1+rn-2xn-2+…+r1x+r0 is serially transmitted to SC block with the sequence of rn-1, rn-2,…,r0. Every partial syndrome is calculated with shown multiply-accumulate circuits (MAC) in every clock cycle. After n=255 clock cycles, the 2t=16 syndromes are computed and serially transmitted to the next KES block.
Step 2. (Key equation solving): With the help of inputted S(x), in this step, Key equation solver (KES) block will calculate error evaluator polynomial Ω(x) and error locator polynomial Λ(x) by solving key equation: Λ(x)S(x)≡Ω(x) mod x2t. This part is the most important step in the whole RS decoding procedure, which usually dominates the performance of the overall decoder. Therefore, in this chapter, we focus on the algorithm and architecture optimization of KES block.
Generally, Berlekamp-Massey (BM) algorithm or modified Euclidean (ME) algorithm can be employed to solve key equation. To data, many efforts have addressed for efficient VLSI implementation of the above two algorithms. In , BM algorithm was reformulated as RiBM with the same regular architecture format compared with conventional ME algorithm in  and , and a folded BM algorithm based on RiBM was introduced in . Reference  and  implemented conventional ME algorithm with systolic and recursive architecture. In Section 3 and Section 4, based on the above efforts, some improved KES algorithms and their corresponding hardware implementations will be discussed for efficient RS decoder design.
Step 3. (Chien search & error evaluation): After KES block finishes its computation for the current codeword, the calculated error locator polynomial Λ(x) and the error evaluator polynomial Ω(x) will be outputted to CSEE block to generate the error positions and magnitudes.
Chien search is a widely employed approach to look for error position. Its basic idea is simple but efficient: If Λ(α-i)=0 for current i, it indicates that the i-th symbol of the received codeword is wrong and needs to be corrected. After obtaining the position of error, the following Forney algorithm is applied to determine the error value:
where Yi is the error magnitude for the i-th erroneous symbol.
Based on the above described Chien search and Forney algorithm, the architecture of CSEE block for example RS (255, 239) code is illustrated in Fig. 2. It consists of several unit cells (shown in Fig. 2(a)). Both of the sub-blocks that carry out Chien search and Forney algorithm consist of these basic cells. In the beginning, λi, and ωi, (represented by Ui in the figure), as the coefficients of Λ(x) and Ω(x), are parallel loaded into these basic cells (enable=1). Then, during the next 255 cycles, those basic cells will carry out multiply iteratively. Fig. 2(b) is the overall architecture for CSEE block. Once a zero is detected in Chien search, the corresponding error magnitude will be computed via executing the above Forney algorithm.
The overall architecture of RS decoding is summarized in Fig. 3.
As mentioned in previous paragraph, since KES is the dominating step in the whole RS decoding, Section 3 and 4 will focus on the algorithm and architecture optimization of KES block.
For short-distance optical transmission, such as 10GBase-LR, since the noise rendered from transmission distance is quite limited, the requirement of coding gain is not as strict as long-distance backbone network (which will be discussed later). Therefore, as discussed in Section 1, Reed-Solomon (255, 239) code is widely used in this kind of network due to its high code rate and good error correction capability.
Although coding gain is not the major concern in this scenario, because of limited hardware resource, in order to implement efficient RS decoder, the designers have to consider the challenge of achieving high data rate with low hardware complexity. Accordingly, optimization of RS decoding architectures is necessary for high-efficiency hardware implementation.
In this section, based on the two main RS decoding algorithms, the improved ME-based and BM-based decoders are introduced.
In traditional ME algorithm, the inherent degree computation and systolic architecture renders large consumption of area and power (see  and ), which is not suitable for the discussed application. To reduce the unnecessary degree computation, DCME algorithm was introduced in . By generating internal switch and shift signals, the DCME algorithm can achieve the same function as ME algorithm without degree computation.
It is needed to point out that the initialization of DCME and ME is different due to the consideration of the design of the following introduced FSM.
Fig. 4 shows the FSM for generating control signals. In each iteration, there are two possible states: S0 and S1. S0 represents the case when both of ai and bi are nonzero; otherwise the state of FSM is S1. The different combinations of the current and previous states will determine control signals in the current iteration.
When the leading coefficients of Ri and Qi are both nonzero, it denotes that polynomial computation can be carried out (pc=1), otherwise shift operation would be performed (pc=0) to reduce leading coefficient (and in this case the leading coefficient must be zero, the details will be shown in next paragraph). In each iteration, the possible shift operation would be executed once at most. The whole shift process would not stop until both of ai and bi are nonzero, which means the degrees of Ri and Qi are equal again. And in that case KES block starts executing polynomial computation. So it is clear that in each iteration the algorithm would perform only shift operation or only polynomial computation operation.
It should be pointed out that after every polynomial computation, if being carried out, the original leading coefficient of Ri+1 must be zero due to the arithmetic character of Ri+1 = biRi + aiQi. Different from the leading coefficients referred in above paragraph, this kind of leading zero is a “false” leading coefficient which will cause logic errors in next iteration. (For example, after polynomial computation if Ri+1 is represented by 0, 0, 0, α2, α3, the “false” leading coefficient is the first zero, and the real representation of Ri+1 should be0, 0, α2, α3.) So in every possible polynomial computation process, the designed rDCME KES block has automatically eliminated this kind of leading zero with the aid of “start” signal in hardware design (Fig.5): the coefficients which arrive simultaneously with “start” signal are selected as the leading coefficients. So once polynomial computations are finished, by delaying Qi+1, Ui+1 and start signal one more clock cycle, the “false” leading zero is eliminated, and degRi+1 is one less than deg Ri or equal to it (this condition happens when the previous iteration’s actual input is xRi brought by initial input R0=xS(x)). Then ai and bi represent the real leading coefficients respectively.
If the previous state and the current state are both S0, it indicates that the polynomial computation is able to be executed in the two successive iterations. So pc=1 since the current operation is polynomial computation. Due to the fact the previous state is S0, after the previous polynomial computation and the degree reduction, degRi is one smaller than deg Ri-1 or equal to it. So deg Ri is the same with degQi or one smaller than degQi. These two possible conditions occur successively and the switch signal (sw) alternates successively (sw=~sw).
If the previous state is S0 and the current state is S1, KES block would process shift operation to eliminate leading zero (pc is set to 0) in the current iteration, because S1 shows leading coefficient is zero. sw is also 0 because switch operation always be carried out with polynomial operation.
If the previous state and the current state are both S1, it indicates that the two successive iterations are both in shifting operations. Similar with the above condition, sw and pc are both set to 0.
If the previous state is S1 and the current state is S0, the polynomial computation would be executed (pc=1) in the current iteration. Since in the previous iteration Ri is in shift operation (Qi is never in shift operation because of its character in polynomial computation, it is also guaranteed by rDCME’s initial conditions), actual degree of Ri must be smaller than Qi, so sw is set to 1.
After 2t=16 iterations, the rDCME KES block stops and outputs error value polynomial R(x)=Ω(x) and error locator polynomial L(x)=Λ(x).
Fig. 5 shows the detailed architecture of rDCME algorithm. The KES block is designed with single PE. It is commonly known that recursive architecture usually can not be pipelined due to data dependency. And recursive architecture is always a bottleneck for high-speed. However, in the rDCME architecture, these disadvantages can be avoided. A 11-stages (2t-5=11) shifter registers are used to store the last iteration results and feedback to the next iteration for avoiding dependency between successive iterations: At the end of each iteration, the leading coefficients of five updated inputs (R, Q, L, U and start) are just stored back into the leftmost registers of shift registers and ready to be updated in the next iteration. Because during the computation procedure the whole iteration process of KES block is a close loop, the property of leading coefficients’ in-time arrival makes dependency between iterations be avoided and logical validity guaranteed. Furthermore, because the former SC block takes n clock cycles to output one codeword, the PEs in conventional systolic DCME architecture in  and  are idle in the most of processing time and at the same time it occupies a large amount of chip area. So the multi-stages pipeline can be employed in the area efficient recursive KES block with valid logic and only a little data processing rate degradation. Note that in Fig. 5 the multipliers are pipelined.
Table 1 presents performance comparisons between the rDCME RS decoder and other existing RS decoders. It can be observed that the rDCME decoder has very low hardware complexity and high throughput. Compared with the existing ME architectures, the total gate count of the rDCME architecture is reduced by at least 30.4%. Therefore, the hardware efficiency is improved at least 1.84 times, which means under the same technology condition our design would be much more area-efficient compared with other existing RS decoder designs for multi-Gb/s optical communication systems.
Besides ME algorithm, BM algorithm is another main decoding approach for RS codes. An important and inevitable disadvantage of traditional iBM/RiBM algorithms is the high cost of area or iteration time for computing error value polynomial Ω(x). In iBM architecture stated in , one third of total iteration time or half of hardware complexity is employed to compute Ω(x); in RiBM architecture stated in , one third of processing elements (PE) are utilized to calculate and store Ω(x). Therefore, the calculation of Ω(x) impedes further performance improvement of current BM architectures.
In each iteration, scratch polynomial B(x), discrepancy δ, error locator polynomial Λ(x) and its coefficient λ0 are simultaneously updated. After completing iteration, KES block outputs them to CSEE block for calculating error values Yi. So the computation of Ω(x) is completely eliminated, which enables KES block to reduce a large amount of extra computation circuitry and iteration time.
Furthermore, in order to reduce hardware complexity significantly without sacrificing throughput per unit area, pipeline interleaving techniques in  is employed in the PI-iBM algorithm and architecture proposed in .
As depicted in the following PI-iBM algorithm, interleaving factor g is a crucial factor to design overall architecture. In practical RS (n, k, t) codes, such as (255, 239, 8) code, t=8 is a common value. So in this paper we set both p and g as 3 for demonstrating PI-iBM architecture.
The PI-iBM architecture consists of two blocks: pipeline interleaving error locator update (PI-ELU) block and pipeline interleaving discrepancy computation (PI-DC) block. As it is illustrated in Fig. 6, PI-ELU block is designed to execute Step3 for updating polynomials. Fig. 6(a) shows the internal architecture of the i-th PE. Initial values of upper and leftmost registers are shown in the figure and other registers are initialized to zero. For the i-th PE, in each iteration 10 cycles are required to update the stored coefficients of Λ(x) and B(x), meanwhile “ctrl” signal is set to be “1 0 0 0 0 0 0 0 0 0”. At the beginning of r-th iteration, b3i(r), b3i+1(r), b3i+2(r) are stored in the leftmost three registers with λ3i(r-1)γ(r-1), λ3i+1(r-1)γ(r-1), λ3i+2(r-1)γ(r-1) in the upper three registers, then they are shifted in the upper and lower loops to be updated. During the first 3 cycles, λ3i(r), λ3i+1(r), λ3i+2(r) are successively computed and outputted to PI-DC block for calculating discrepancy δ(r) (Step 1). After current iteration is completed, b3i(r+1), b3i+1(r+1), b3i+2(r+1) and λ3i(r)γ(r), λ3i+1(r)γ(r), λ3i+2(r)γ(r) are just fed back to the initial registers which stored them at the beginning. The two dashed rectangles indicate that the critical path between lower multiplier and adder has been 3-stage fine-grain pipelined; the path between upper multiplier and adder is tackled in the same way.
In addition, PI-DC block mainly implements the function of updating discrepancy δ(r) (Step1). A low-complexity and high-speed architecture of PI-DC block is shown in Fig. 7. As shown in Fig. 7, 2t-1 syndromes are serially sent to PI-DC block and shifted in the upper t+1 registers every 10 cycles. The initialization of leftmost register is S0 while other registers are initialized to zero. In each iteration “ctrl 1”signal is set to be “0 0 0 0 0 0 1 0 0 0”. In the first 5 cycles of each iteration, input λj, λ3+j, λ6+j and corresponding syndromes selected by multiplexers are multiplied by three 3-stage pipelined multipliers (shown by dashed lines). At the end of 6-th cycle accumulator circuit computes δ(r) and outputs it to control block for updating γ(r) and SEL(r). Passing another register which cuts path between PI-ELU and PI-DC in control block, the three signals are fed back to PI-ELU block. In the overall architecture of PI-iBM (Fig. 8), it takes 7 cycles to calculate and output δ(r) (PI-DC block), and another 3 cycles is the cost for calculating new coefficients (PI-ELU block), so the total time for one iteration is 10 cycles.
Table 2 gives the implementation results of PI-iBM decoder and also lists some other designs. From this table we can find that the PI-iBM architecture deliver very high throughput with relatively low hardware complexity: the total throughput rate and throughput per unit area in the PI-iBM design are at least 200% more than those existing works. To achieve data rates from 10 Gb/s to 100 Gb/s, PI-iBM decoder has the lowest hardware complexity. If 65 nm CMOS technology is used in the implementation, the throughput of our design can be increased significantly. Thus the current designs can fit well for 10 Gb/s-40 Gb/s optical communication systems. For 100 Gb/s applications, we may need two to three independent hardware copies of the designs. However, the PI-iBM architecture will remain to have the lowest hardware complexity compared with existing designs. In short, the PI-iBM decoder is very area-efficient for very high-speed optical applications.
|Total of gates||fmax (MHz)||Throughput (Gb/s)||Latency (cycles)|
|Retimed iBM in ||0.18||8423||654||5.23||288|
RiBM in 
|Systolic ME in ||0.13||102500||770||6.16||80|
|Folded ME in ||0.13||17000||625||5.00||256|
For mediate distance optical network, such as Metro Ethernet network, traditional RS decoding can not provide enough coding gain for the data transmission in this scenario. Instead, enhanced FEC scheme should be employed for improved error-correcting capability. Notice that in this kind of systems, long burst error is the major error pattern in transmission procedure; therefore, burst-error decoding algorithm and architecture are attractive solutions for this case. In this chapter, we introduce efficient burst-error-correcting RS decoder to meet the requirement in this type of application.
As excellent Maximum Distance Separable (MDS) code , RS code is very effective in correcting long burst errors. However, previous RS burst decoding algorithms in  and  are infeasible for hardware implementation due to their high computation complexity. In , Wu proposed a new approach to track the position of burst of errors. By introducing a new polynomial that is a special linear function of syndromes, this approach can correct a long burst of errors with length up to 2t-1-2β plus a maximum of β random errors. Here β is a pre-chosen parameter that determines the specific error correcting capability. In this case, the miscorrection probability is upper bounded by (n-2f)(n-f)β2m(β+f-2t).
Although the approach in  has reduced computation complexity, it still contains inversion operation and long data path, which impedes its efficient VLSI implementation, therefore, the algorithm in  was reformulated to the RiBC algorithm. The RiBC algorithm is a kind of list decoding algorithm. 8 polynomials are updated simultaneously in each iteration. After every 2β inner iterations, , as the candidate of the error locator polynomial of the random errors, is computed for current l-th outer iteration. When l reaches n, we track the that is identical for longest consecutive l, and record the last element l* of the consecutive l’s. Then the corresponding and at the l*-th loop are marked as overall error locator polynomial and error evaluator polynomialrespectively. Finally Forney algorithm is used to calculate the error value in each error position with the miscorrection probability up to (n-2f)(n-f)β2m(β+f-2t.
The RiBC algorithm is targeted for correcting burst error plus some random errors. By observing step2.3 and step 2.4, it can be founded that both of them are quite similar to the essential update equations in RiBM algorithm (see ). Therefore, it inspires us that both of the RiBC algorithm for burst-error correction and RiBM for random error correction can be implemented one the same hardware. Furthermore, considering single burst error correcting algorithm in  is a specific instance of RiBC algorithm with β=0, so it can also be implemented on the RiBC architecture. Accordingly, a unified hybrid RS decoder, which can be configured to the above three types of error correcting mode, is introduced in the next subsection.
The overall UHD architecture is shown in Fig. 9. Here different blocks are used to process different steps in algorithm. Since excluding KES and PT blocks, other blocks are quite straightforward to be implemented; in this section we only introduce the architectures of KES and PT blocks and focus the discussion for the case of RiBC work mode. Interested readers can refer to  for the introduction of other blocks and other modes.
For RiBC algorithm, KES block is employed to carry out steps 2.4. Fig. 10 presents the overall architecture of KES block and the internal structure of its two types of processing elements (PE): PE0 and PE1. As shown in Fig. 10(a), the KES block consists of 2t-1 PE0’s and 2t PE1’s. In the r-th iteration, each register in PE0i/PE1i stores the corresponding coefficients of different polynomials (Fig. 10(b) (c)). For each outer iteration, it takes 2β cycles to compute and as the coefficients of and. Meanwhile, will also be computed and outputted into PT block to track the longest consecutive that are identical.
PT block is used to track the longest consecutive polynomials that are identical (step 3). Fig. 11 illustrates the architecture of PT block. The input, andfrom KES block at the l-th outer iteration are denoted as, and. In addition, represents, while are the coefficients of current continuously identical. Moreover,stores the coefficients of current longest continuously identical. Control signals shift and equal are generated from the signal generation schedule. After l reaches n, and are outputted as the coefficients of overall error locator polynomial and overall error evaluator polynomial.
Table 3 presents the comparison between UHD and RiBM decoder. Here for the example RS (255, 239) code, n=255, t=8 and m=8. The hardware complexity is estimated based on the work in . Although the area requirement of the UHD decoder is about 1.7 times of that of the RiBM decoder, the UHD decoder can achieve significantly enhanced burst-error correcting capability. In the channel environments that likely generate long burst of errors (f>8), the traditional RiBM decoder fails to decode the codewords for its limited error correcting capability, while UHD decoder can be still effective. In short, the UHD design provides an efficient and attractive unified solution for multi-mode RS decoding in optical applications that demands enhanced error correcting capability.
|Total gates(# of XOR gates)||34308||18968|
|Critical path (# of gates)||10||8|
|Latency||4846||Unavailable to decode|
(the worst case)
|Unavailable to decode|
(t ≤ 8, 2t+ρ≤16)
For long-haul optical transport networks (OTN), because the performance loss mainly results from long distance transmission, the requirement on coding gain is very strict. This requirement even gets more and more strict when optical backbone networks enter 100Gbps era. Based on OIF whitepaper, the new FEC schemes applied in 100G long-haul systems should achieve waterfall performance at very low BER region. Meanwhile the other requirements for OTN FEC such as capable of achieving very high speed and having very low error floor still remain. Therefore, 100Gbps era puts more challenges on FEC schemes. In this section, some recent FEC schemes targeted to 100Gbps applications are introduced.
One candidate for 100Gbps application is BCH-based binary product codes such as the one presented in . The component BCH (992, 960) and (987, 956) codes are constructed carefully over GF(210) for hardware amenity, which have the 3-error correction capability, therefore its decoder design can be developed based on simple PGZ algorithm in . The simulation results show the performance of this FEC scheme can be very close to the Shannon limit.
The above binary product scheme is based on hard-decision. If soft information is available in the system, soft-decision decoding approach can work with the product codes to enhance the overall decoding performance. Fig. 15 illustrates a LDPC code concatenated with BCH-based product code for long-haul network systems in . In this scheme, LDPC code is used as inner code and BCH-based product code is used as outer code. Some other soft-decision based concatenated FEC scheme such as RS code concatenated with LDPC coding system in  can also provide significant coding gain for targeted ultra high-speed optical communication.
With the evolution of optical network, the employed FEC scheme has been developed in several generations. The requirement on high data rata and large coding gain is always challenging the design for efficient FEC decoder. In this chapter, targeted to different types of optical transmission networks, ranging from local Ethernet to long-haul backbone system, different FEC solutions with efficient VLSI implementations are discussed. For short-distance networks, two kinds of area-efficient high-speed RS decoders are analyzed for the scenario. For mediate distance networks, which require some tradeoff between decoding performance and hardware efficiency, the introduced RS burst-error decoder can be employed to meet such requirement. For long-haul systems, which have stringent requirement on decoding performance, some candidate FEC schemes targeted to the future 100Gbps era are discussed. In summary, these various FEC architectures and schemes are good candidates for their specific targeted optical transmission applications.
2157total chapter downloads
Login to your personal dashboard for more detailed statistics on your publications.Access personal reporting
Edited by Narottam Das
By Xiaobo Xing, Huaqing Yu, Debin Zhu, Jiapeng Zheng, Huang Chen, Wei Chen and Jiye Cai
Edited by Narottam Das
By Vjaceslavs Bobrovs, Jurgis Porins, Sandis Spolitis and Girts Ivanovs
We are IntechOpen, the world's leading publisher of Open Access books. Built by scientists, for scientists. Our readership spans scientists, professors, researchers, librarians, and students, as well as business professionals. We share our knowledge and peer-reveiwed research papers with libraries, scientific and engineering societies, and also work with corporate R&D departments and government entities.More about us