Forward Error Correction (FEC) techniques for …

1 1 Bell LaboratoriesForward Error Correction (FEC) techniques for optical communicationsIEEE High-Speed Study Group Plenary meeting, MontrealJuly 1999 Kamran Azadet, Mark YuLucent TechnologiesPhone: 732-949-7280 Email: LaboratoriesOutlineqWhy FEC ?qCyclic codes - OverviewqAlgorithms and implementationqEncoderqDecoderqPerforman ce analysisqLatency issuesqSummary3 Bell LaboratoriesWhy FEC ?4 Bell LaboratoriesWhy FEC ?qFEC lowers BER by a great deal for low for RS(255,239) overhead is 6%: For input BER=10-4, outputBER=10-14 !qVery low overhead codes exist (less than ) and have beenwidely used in other optical communication applicationsqPossible trade-off between performance and overhead (illustrated in thistalk)qOverheadqincreased rate -> slightly reduces the overall coding gainqelectronics cost (MUX/DEMUX if line rate is increased)qadds FEC circuitry (encoder is simpler than decoder)5 Bell LaboratoriesHow to incorporate FEC in 10 GbE ?qWAN applications incorporate already FEC, solutions arecurrently proprietary.

2 There is however an on-going effort toadopt an in-band FEC standard in 10G SONET (most likelybased on a BCH-3 code)qThere may be ways to exploit already existing overhead in theEthernet LAN (IPG?)qHowever available overhead may be limitedqEthernet packets are variable size -> decoding would be more complicated !qFor increased performance, line rate could be slightly increasedqfixed length blocks are preferableqFEC can be combined with constrained codes such as 8b/10b(or 16b/18b), or with zero-overhead scrambled LaboratoriesCyclic codes - overview7 Bell LaboratoriesSome FEC definitionsqSystematic block codeqAn encoder accept k information symbols and appends separately a set of rredundant symbols (parity bits) derived from the information symbols. Note theinformation word is not disturbed in any way in the encoder. This code is called(n, k) code, where n=k+ code space is enlarged and codewords are a constrained subset, errordetection and Correction is possible based on maximum likelihood distance of two codewords: number of non-zero elementsin the codeword formed by their differenceqHamming distance of a code = d (is the minimum distance betweentwo codewords)qSingleton bound:d n - k + 1 Information bitsRedundantbitsknr8 Bell LaboratoriesSome FEC definitions - codeqAn (n, k) code is cyclic if a cyclic shift of a codeword is also a with a generating polynomial (usually implemented as LFSR)qTwo representations of a codeword w= (w0,w1.)

3 , wn-2 , wn-1) <->W(x)=w0+w1x+..+wn-2 xn-2 + wn-1 xn-1qExamples of popular systematic cyclic block codes: binaryBCH, Reed-SolomonqReed-Solomon is famous for its ability to correct bursty LaboratoriesGalois fieldsqTheory developed by french mathematician E. GaloisqGalois Fields: for a prime p, GF(p) denote the integer ring(over [+,x]) modulo pqExample: GF(2): addition is modulo-2 addition / XOR-gate multiplication is modulo-2 multiplication / AND-gate Simple codes such as Hamming codes or binary BCH codesare built over GF(2).qGalois Fields definition can be generalized to GF(pm), forinstance GF(28), where words are Bytes and not bits (this isused in Reed-Solomon codes)10 Bell LaboratoriesHamming codeqThe well-known (2n-1, 2n-n-1) code with Hamming distance of 3is capable of correcting 1 errorqError syndrome gives the Error locationqEasy to decode, but only correct one errorqAre there codes able to correct more than one Error and easy todecode?11 Bell LaboratoriesRS codeqRS(n,k) consists of all polynomials of degree at most n that aremultiples of the generator polynomial g(x) = (x-1)(x- 1).

4 (x- 2t-1), where is a primitive element ofGF(2m)qMinimum distance between codewords is d=n-k=2t+1, thusRS(n,k) can correct t symbolsq2t Erasures can be corrected (an Erasure is an Error with knownposition)12 Bell LaboratoriesBCH codesqThe cyclic code of length n over GF(q), n coprime with q, whosegenerator polynomial is g(x). RS code is a subclass of BCHcodeqBinary BCH code: a BCH code on GF(2), , q=2qBinary BCH codes are most popularqBCH codes usually correct few bits in a block (1- Error correctingor Hamming, 2- Error correcting, 3- Error correcting, etc.)qEncoding and decoding procedures are similar to those of RScode, except there is no need to compute Error magnitude forbinary BCH code13 Bell LaboratoriesAlgorithms and implementation- Encoder -14 Bell LaboratoriesRS encodingqSend W(x) = xn-kD(x) - r(x), where D(x) is the informationsymbols, and r(x) is the remainder of xn-kD(x) divided by thegenerating polynomial G(x)qW(x) is a codeword, because G(x) divides W(x)qW(x) is systematic, , redundant symbols are added after informationsymbols15 Bell LaboratoriesRS encoding (2)qRS is a cyclic code and often implemented as a LFSR withGF(2m) operators16 Bell LaboratoriesAlgorithms and implementation- Decoder -17 Bell LaboratoriesRS decodingFirst some more definitions:qError word polynomial e(x) = e0+e1x+.

5 +en-1xn-1qThe received word polynomial is given by w(x) = c(x) + e(x)qSyndromes Sj=w( j) = for j = 0, .., 2t-1qSyndromes can be computed using the Horner algorithm: =10niijie 18 Bell LaboratoriesRS decoding - that there are r errors , r <= t, occurredqat locations i1, .., ir (let Xl= il )qwith values ei1, .., eir (let Yl = eil il = eil Xl )qReformulate Sj = ==> 2t equations for 2r unknowns, r<= t =rijiile1 = LaboratoriesRS decoding - Error locator polynomials(x) = (1-xX1)(1-xX2)..(1-xXr) = srxr + .. + s1x + 1qInverse of zeros of s(x) gives Error locationsqMultiplying both sides with YiXij+r and letting x=Xi-1=> s(Xi-1 )=0,for all i,j, we getqM is singular if m>r !qSo we can determine how many errors have occurred = ++ ++ LaboratoriesRS decoding steps1. Compute Syndromes Si= w( i), for I=1,..,2t2. Determine the maximum number r so that M is nonsingular. r is then the number of errors Find the coefficients of the Error -locator polynomial (solving the key equation) by computing4.

6 Solve s(x)=05. Find Error locations6. Compute Error magnitude at Error locations and correct theerrors ++ LaboratoriesRS decoder architectureErrorDetectionErrorCorrectio n22 Bell LaboratoriesMore on RS decoding algorithmsqClearly finding |M| and M-1 is not easy for large tqFortunately, RS has been researched and widely used in manyapplications for a long time, therefore there are more efficientalgorithms for each ,qto solve the key equation ----> Euclidean algorithm, Berlekamp algorithm,Berlekamp-Massey algorithmqto find roots of s(x) ----> Chien Search algorithmqto compute Error magnitude -----> Forney algorithm23 Bell LaboratoriesPerformance analysis24 Bell LaboratoriesPerformance = BCH(8191,8178)BCH-2 = BCH(8191,8165)BCH-3 = BCH(8191,8152)RS-4 = RS(255,247)RS-8 = RS(255,239)RS-16 = RS(255,223)UNCODED25 Bell LaboratoriesRS codes: simulated results26 Bell LaboratoriesAn alternative representationqThe above coding gains (in dB) do not map directly in opticalgain (in dBm)qOptical gain depends on channel and receiver responseqUsually optical power is proportional to detector current, and notto electrical power !

7 QInput BER versus output BER is a unique representation ofthe performance of a given code. It does not depend on opticalresponse. It is very useful for comparing the performance ofdifferent codes with variable size / LaboratoriesInput BER versus Output BERBCH-1 = BCH(8191,8178)BCH-2 = BCH(8191,8165)BCH-3 = BCH(8191,8152)RS-4 = RS(255,247)RS-8 = RS(255,239)RS-16 = RS(255,223)UNCODEDBCH-2 BCH-3RS-4RS-8RS-16 BCH-128 Bell LaboratoriesLatency issues29 Bell LaboratoriesLatency issuesqLatency is obviously implementation dependantqIn many cases, total latency of encoding + decoding can be onthe order of 2n-3n (n block size)qFor instance for RS(255,239) total latency could potentially be~3x255x8x100ps < 1 sqSome existing FEC chips used in WAN have 30 s total latency(longer blocks, lower overhead)qPropagation time in fiber:q300m -> 1 sq3km-> 10 sq30km-> 100 sqIn LAN applications, smaller block sizes are preferable (tominimize buffer size).30 Bell LaboratoriesSummary31 Bell LaboratoriesSummaryqConventional FEC schemes can achieve 6dB coding gain ormore without need for soft decisions qError Correction on the decode side is up to implementersqParity check could be used to perform bit alignment (in a serialapproach) or de-skewing (in a WDM approach)qParity check could be used to indicate link qualityqClear trade-off between FEC performance on one hand and[complexity,latency,overhead] on the other handqSimple FEC codes exist (Hamming, binary BCH)qBCH & RS codes can be (are) implemented in generic CMOS technology