View All Documents & Correspondence
Forward Error Correction Encoding For Multiple Link Transmission Compatible With 64 B/66 B Scrambling
Abstract: Abstract FORWARD ERROR CORRECTION ENCODING FOR MULTIPLE LINK TRANSMISSION COMPATIBLE WITH 64B/5ftB SCRAMBLING A Forward Error Correction (FEC) code compatible with the self-synchronized scrambler used by the 64B/66B encoding Standard for transmission on Serilizer/Beserializer (Serves) communications channel links. The FEC code allows encoding and decoding to occur before and after scrambling, respectively, as to preserve the properties of the scrambling operation on the transmitted signal. The code allows the correction of any single transmission error inspire of the multiplication by three of all transmission errors due to the 64B/66B scrambling process. A Hamming code is combined with a Bit Interleaved Parity code of degree n (Blip-n). these two codes provide for protection both for an error anywhere in the maximum length of the packet as well as for an error replicated two or three limes by the descrambling process. All single bit errors wither multiplied or not, have unique syndromes and are therefore easily correctable. In addition, the packet can be transported across multiple serial links for higher bandwidth applications without a degradation of the cede efficiency, The lionizing code can be generated from any irreducible polynomial such as ll(\) = x1 + 1. The BIP code is chosen to be of degree 6 to fit with 64B/66B scrambling polynomial and is represented by B(x) = x + I.
Notices, Deadlines & Correspondence
Patent Information
Applicants
1. INTERNATIONAL BUSINESS MACHINES CORPORATION
Inventors
1. DELL, TIMOTHY, JAY,
2. GLAISE, RENE,
Specification
KORWAfiD ERROR CORR£CTl<)N FNCODINC fOR MULTIPLF. TJ\K TR.\\SMTSSrONCOMCATIBtEMITHr.4Rvli6RSCR.AMEllJNG
FIELD OF THE IN\'ENTlON
The field ofiJicinvemiun is related to b'\\:h spL:i?d digital comniunk'^Jbn systems, .-ind more paiiEcularly to improved iirici-idfni| (echniques to enhanci: rdi^biJiiy oft]-an^iniiii;:d jignal^Vy torrccling mullifliCLiiion afsin^le bit errors caiiMjd by bil error spread] nij dur lo j^elf-Hynchromzed Hcranibl[[ig.
MCKCROI )\n OF THE INV E^TlU^
In digital communication* .sysiems. ihc transmissinn of data j^ subjuoi Ui "oniipxion and ejTors due to rhe presence of noise in ilie ci^mmunicaiion dinnncl. Scrambfing, used to facilitaie accurdle reception of [he Mi^nal at iln: debliniilion. introduces: additional ermis through a process kno\^n as error sprendin^. In such systems, it Ls common lo encode iTio tran.^niiued signal at the source using redundant pant}' bits to allow com^uiion of ihe errors. A digital bit stream i.s typically parsixl into fixed Icnijlh datawordsof nbitsb^sedon a maximum length for which ibc system receiver can extract a cloc-k signa] liming reference from Ihe transmitted data. With die concatcnalion of redundant bits the encoded digiial word of m bits Ls longei* than the original dataword.
Onoof the challenges in providing error correction for high-speed links is thai any error correding checkbits appended to the dataword being protected also need to be considered for their effect on ihe bit transition dcji:>iityofthc physical layer Typically, in order to maintain synchmniraiicin with ilic proper posilion within H packet boundaiy to strobe data, a minimum number of transitions Irom 0=>\ or from J=>0 mast be observed. A Jong stream ofO\s. for example, may cause a receiver to losetrackof when to .sample the incoming data. Thus when a I is ultimately iransmiucd^ the rect^iver may have Inst synchronization and fail [0 detecl the 0=>J iransilion
Itiorderto prevent loss of synchronizalion, an encoded dataword may be processed
by one of several knnwn scrambling techniques. A self-synchronized scrambler is nften
implemenicd -^[[h a Linear feedbac;- ^■- '.) P J^i^Ie^(L^■SK^ ihai is pro^ramm^d lo muliipjy ihe dalawoid dtv^rdin^ lo a piedi::";n^^ poly-:ioin:al to casj^c a marbemaMcally yiiiiranieed nii[LimLLrn number of hit rmn^iliom.. The scranilikrLFSR canaba bepic^oi lo ^ specific value lofurih^T enhance the number ofbirlraTiiiiion-S for all al]-/i-Tu daia payload. On ih^ rcci-ivinj: side, rhe payload rnusf be descramb[ed. u.^ualJy b> " similar [nverjje pioco.^s. where (hebJTstreani is divij!:d by rhe same pcedetlocd poljnumiaL
Data scrambling is U.M^J (U maintain clock liyncliTont^iioii bi^iiAijtn Ihe n-an.-.mmer and receiver. For ihe reasons stated above, data ■ncrambliiij; algorithms usually limit Ihe maximum number of ?^equentialfy Jrarisuiiilod ones or zeroi^- ^u^b ihai a minimum number uf io^jc n-anjniiions may bo rtoognized for successful extraclifnof the iran.tiniiEJed doe^. L[milin[i lh^ maximum number of biLs havnit; liie sariko valiio onubk-s Iho receiver 1o maintain riynchronizacion wiili ihe Mjuree.
Alihough scrambling is helpful in reducing receive! drift, il provides an additional ^urce of Iran.smir^silon crmr;^ bt^cau^e single bii errors oeCLJi'i"i"£- ii^ iheoiiginal daca sEreani dre multiplied throui^h the scramblinj; process. The multiplication of a ^injile bit erroroccurs because the scrambling and de?crambiing functions rely on each bit of a dataword, including a bii ihai is ir i;rror when rooonsrrticiing Ihe original iraiisniiHi^d data. The muitiphcation of single bit errors in this fashion is known as "bit error spreading" and oecur^ at the receiver v^hen a descrambler attempts to restore the ssemmbfedsi^flllo ilsorii^inal stale
Til order lo insure iliai all nf the bitfltream is propsrW scrambled, any error eorre<:tiTig code (ECC) eheckbits appended lo ilie daraword niusi aL^o be scrambled. This necessitalei that scrambling be done after the ECC chcckbils are added !*> Hic iransmitlcd word I he iraiiimified daEa\^ord is likcwLse dcscrambled ai Ihe receiver prior to aclivalint; .vhaievcr BCC scheme is implemraled in Ihe receiver. In this manner. Ihe bit transmission denl^i1y i^ maintained for the entire packet, and nut jusi the daiabit portion of the packet.
An exemplar prior ait cvtmmunications system is SHO^T" "" F'S^ 1 ^ ^'berem (Physical Codinji Sublayer) upper inteiface 100 represents a tO gigaf^it media independeni inierfaoe (XCMII) that provides an interface for dalH communicalions equipment irrespective of the
pfty^ji;^] jnudc of iran^pon -A ii'.-: :?■ ''^e '^ry^rded J 02 or received 104. i'he enoodei 142 and gearbox H(i funciions are nece^'i . to inj[- :iala and cniitrol chj^racterto i he blocks and to iidapl fni"mal.- Thi^y aro riol iiei^Lrsstcr^ lo \hc uadof.irtndin^orihc invcniion and are not funher described. Receive paih 150 inciudej! the dejicrambler 154 to i-ecoverthe oiiginal stream of bitri. PC^ 120 also iricluiii^^ a fuEiciioii 160 in nioniior bii enor rafo nvvr \h^-iL-aiisniL«ion incdiuin and ilicrc 15 ij di^i-odi; I'nndion 152 \:h
Tho.se skilled in Ihe ail \^ill lealize dial although the mventbn is described in the pa-riieubr ix>nlc>;t of lOGbH il oould be praoiieed as wdE in a different environment and will know, from the detailed desciiplion infl-a. how to adapt it 10 olher appliualions espetially, for applicatioas uhere a different scrambling polynomial would be used.
Durjjur Ihc physical iran.^irnission of the payload. random, single-bu errors are common. Thiis ii due to the extremely high speeds employed in conimunicaiions channel.s used today. If there were only one error in the data packet, then a simple Hamming ECC would be able lo coireei all such errors. Becuuse self-synchronized scrambJcr^ mul:iply errors, A more robu&l solution isTixiuircd ai ihc recciverlo handle the incident error and any replicated errors.
On the receiving end. \^hieh could be in the same logic chip or on a completely different logic ebip, Ihc rx;eeived pactci is fir.sl synehmnized and the packet boundaries detected. The invention doca nol assume any particular rnclhoci for delineating packet
botiiidane^. Of^en, 'j,-kL-" I'lK^d >-.Zi r;-:'J -■^- ^"e L-^asmiilc^j. (lackm bouii<.Uri<^ ire def^fcfcii on thL^liasisof Ihe added r^-LlimJinE r/- =iid -■■icoaing of Ihi: daia su-eam. Thcru in oi-deno keep the bil erTt>f rdle (BER) i^- low aspos'^iblc, the pjcket L>reLi:i\ed using d predijlined bit Ir^nsiiion density fledvi-ri fmmthe strjimblinE sl«p. The received packt^l i^ descrambled ^nd Then decoded to allo^' for die correction of any ouors mihebil stream.
ho-vvever. -.jb nieiuioncd above, ihc doserambIin^^ process hati ih;: midcriiiable cffeet nf causiEi; ^\iy sjngJe-bJi erri^r.s iJiar were JnlrodiJi:?^ in 111? vhiiine\ during trajj^iu.^.sjon to b? rephcated aecuriiingto the numbi:i of lenn,s ^nd degree of the seTamblingpolynmiUed sequence. If Ihe imiial error oeeur^ towards the ond of the pay load, il will slill bo i^pread, h(}n'cn'ei\ on}y the first accurrsnce may faJ) in the i:}jrrens packei. ]cad}iig to on]y s -imgis bis error, ^jonclhelesg, the replicated manifcsiatiotLsof rhe erc'Oi will dii^i fall lulo the ne\i diila packet and c^use a doubic-bil cnvn- Ihcrc. Ineidi:nt errors in Ihc middie of ihc word can be spread into various double-bit erroii. according to Ihe sctamblirij^ polynomial (Lrid the position of Ihe incideni error.
at read
Another aspect ofdigital communications relHicd to bit tranaiiion density or iriaximum run length is cumulative DCoffscU which reflects die sum of ihe low frequii^ncy vol! ago comporn^nls of the transmilicd data stroum experienced ai ihc receive: r. In binary systems, discreio hgic vslucs for zero ^lid crsic src lypjcsl^y ^ssi^icd fpposile poianty voltages. As a result, wiihoui periodic adjustment, the tumulaiive DC olfsel e\perieni;ed the receiver can migrate toward the positive or negative power supply limit, whtch may to an overload condiiion al the receiver. iTie cumulative DC imbalaiice can be expressed ns the number of bit values required to be inverted to produce a balanced bit stream. If the cumulative n(] offset e:\perieiiced at the receiver can be effectively balanced. Ihc DC voltage swing experienced al the rceei\er can be reduced. In this regard, abi"lnnccd DC offeei can be
v'xploiied (o r£duce o'.oiaU ^iiinii i^ n-.'^? rjiio <>NR) ai xhi reifi^iver because low fri/quency rcuf'^^? mnv Iv rrrrrpi^^/i'ifjr^^!--, :7ii^r.'j ."„: T~':^ i^ jccou'pli'ih^d by eii>iunjtj^ -hs encod-.--d data 111 ream repT^^^cnt^ jb^lnnced diii-T^ution of iogic zero and one values ovvr a fixed unii fif databii^
Foru'ard i;n-or corr^iion {UEC} is a Tcchini^uc dcsiynod to Ldaiiity and correct crrort occurring m the i:-oiiiss oflrrinsmLss^ionihai obviati;^ the step yfre^ndiiig the data bv Ihe iransTYiitier when errors occur. FFC i-i implt^tneiiied "b^ "pplyii^ii ^'i Jl^onlhm in d digital data slR'Jiin to gencraie redundant bits thiii are iraniTniited with the original dita. An idcniical alsoriilini is performed ailhc receiver <:nd of the tvsiein to compare tho (rani'miIted culciihihii jvf ibf£nj^j>ded daf3 wiih the TC'joivsd e^if-'o/iiiig. Tb^ ro.'iuh of The- coiiip3.ri^oii r^ knovMi as the FF<] syridrotne. A null syndroime io mdicstivc fif a rec-^i^ed error-free data a1r<;ii[ri. A non-zero entry in uny bit position of the i:rror syndrome mu^l be intcrprcied to correct imeormore eirors.
The prolilem of bii error spreading is compounded iiinher \vilh the pr^s^iice of TEC at the nec^iver because the total numbi^r of errors m the de&'taniblcd daia stream may exceed [he Cdp^ilnlitv of die FtC dcoodi^i If the error deled ion and ci^rTeciion capability of Ihe ivstem IS exceeded, the on'gmai dfiia is comipied and unrecoverabfe, and musi he retTflji^mmed. Ibi;j-ehy impat-un^ over^]) ^-^y.iteni p^.^rt^l^mJ3J]c^;.
Aiinther factor uffficting tlie correeiion of scn^tnbleddaia across a In^h-speeil coiiimunications link is the practice of running multiple serial hnks in a parallel sTnjciure. It ia becoming moresnd mors comwon^ In ordeno improve oyeT aggrej:aie multiple links to transmit a packet ofdaia ^iimultaneously over several linkfjor bit lanes. In this mannei; the same data payload can be delivered in N.'b fraction of the Hme used for the delivery of apayload over a single link, where N is the time required to Transmit orrf data payfoad orpacfcet across n iHigfe link, and bh Che nunrber (if ftnki\ ft i\ further readily ^ieenthat llie length of the subdivided packet is alto N.'b. In thcoiy. N.^ could be a fractional number, but in praciice. thennriiberof linksis chosen m eonsiderationof the packet siiC (mcluding payload, header and icdundani bitsk, so ii i;* as&umed for thih example ihal b divides IV ev^nfy, and ihercfbre each sub-pactei wiff contain the same or similar
b
niiijiberofhii.^ In Ihis ca.^e. !i, .rd?-:r -^li-iiij: proper bit [jan^ii [cm den.^iiy aiTas^ each phvsicai link, which IS i-&5i,LrcJ 10^-:..-'.-^ ■! -ov. 'ranrimissiOTi BER. [he daiaword Ls spin ,Eiro b .'Ub-d^l^word.s, aiiit 4,;m.-h .-iub-damu nirj is .scrambled and dc^cramblsd iniicpL.'ndenll>. On fhe receive sidi;, Ihe decrambled buWatawords art roconslrucied ic? Ibrrn Ihe original dalatt ofiJ. which 1?^ rliKii decoded for j^i.^sibk- Lirror correction
Ccnain propo.^rals IIJHVC been made lo pmvFdi; »n ECC compatible wjih rhc bit error spreading oi'a scrainbler ■iuch as comrnonly a'isigned Uniled .Siaics Psifi^-nl Application IJS20040!93^97A1, snlirfcd: "ForLvard Error Correction Sdiccnu Compatible u'lth the Bit Error Spreading of a Scrambler," whicK i^ incorpiiraicd bi^Tcin bv refereiice. A dj"iiwhack oT j^ch a schtmi.' is that ii is not able to correct cnuri when Ihe packets ai"e traih'imincd ai^Tosi multiple bitlancs, as mi^nlbncd above
Other applications of FiiC codes tail to iull^ aocoimt for the i:fftc.^^ of bit error spreading attnbutiible to Ihc des^erarfililinji pro<;tss. For cxsmplij. a Net^^'ork Processing Ftm.m paptr fiiibmillcd by Xi^inx ^YV 20l)i.320.00) discloses a 64B.'(»t?B encodei iViirt faiK lo addreis the bit error multiplication problem caused by descrainliling. Anoih^i approach has been taken by thcOpiical Inlt^i^'^'orkinj^ Forum in JoLumuil OIF20CI4.22'> 03. siibmincd by PMC-Sierra, Xilinx, and Sandia National Laboratories, which alio fails to address the multiplication pitiblcm. Similarly, commonly assigned U S. Patent Application 2004/01^3997 A1 di^dujsos a method for tombiniiii^ a simple FFC code with >cram3iling and dListramblin^ ftinclion.s to reduce bit error spreading, but requires transmission ol data packets over a single serial link and therefore propa^^ates bit error information o^£.Tmuliiplo packets. Accordingly, a need exists for a FEC code compatible with 64D^66B >crambling ronml ibai may bo implomtjnlod ov(;ra multi-channel communication system while preserving channel bandwidth efficiercy.
7
SLMMARY or THE [MXNTTO^
A Foiwdi-d tiToi (^orrectinn iFhC:) code compatible witLths scrambler u.sedby the 64B''66B c'Ticoding ilmdard is JisLiusi:J fur (r^jj^mission on Senali?.:;r/Deseriali7er(SeiDesl communicalion links. The 6^B.''66B JiiandarJ enableti Eower ovcrhcid in rL.-njis of the number ofenor conectJOn orpariry bils required (2/(i4 or j%) as compared to 8B.'10B standard cneoriinj^ (2'K i»r 15V..) T)v- proposed FF.C allows encoding and decoding to occur before and after scrjmbhnE^ respeciivelv. r;uch Lhal the resnU^of Iho .sLrambfing operrtliun un ihe tunsinined si^n^i ^i-e pi-e',er\'ed. 1 he code JHOWS the correction of any single Iransmi^sion error iii Spile orihu muliipliciiiion b> ihre;^ of all tran^mir^'iion eiTOn'i due 10 The 64tJ'66B .scramblinji proc^^^^,
Aecordirig to a i1rsi enibodiment. a Hamming code i^ combined with a Bit ln(erli:avi:d Parily codcof dcyrc;- n Lhich IS desirable for higher bandwidth applications without de^radiiig ihe eode efficfency
Preferably^ the iFivention provides a method of appiyinga forward error cotreetion
code to a digital signal for transmission on a serializei-deserializer link, the method comprising: applying a Hamming code to the digital si^al fnjm an irreducible pDl>'nomia3 of the tbrm H(n) = x'" + x' +1; applying a bit-interleaved parity code lo the digital signal of de^ee n [RlP-n); gcncraiing a fir.si checkbit sequence for the eneodt:d digital signaL appending Ihe fit^i ehetkbil sequence to the encoded digital signal; scrambling the eneoded digital .signal antl ihe first chcckbit sequence using n 64B/66B scrambling protocol; iransiJiitting the scrambled and encoded digital signal over (he serializer-deseiializer frnk:
8
(lt:;;crajTihliriti the trJfisjTiiKed di^.^' ----^ i: 2 --jiver ncde. -cn^min^ a second ch^ckhh s^^ue^■^:cL'H^h^^■^c,:1vevrrt^d?. .■'^mp-.... ,W:-/.i^-, checkbn sequence ^M>1I llie secoruS clutkbiL ^eqni.T]i:e: deienjimmg whenL-r ihc irjnsmiikd dii^ildf signal uonuin^ j fTr^r hjT error, and correerrn^ 1 he first b[[ ornjr, a fin^i repliViiied etrorand H second rep]Ji'^ied errot.
Prefcr^biy. tfte invenrion provides a rriL'lhod of buildjnj? i\ forward erior i-orrection fFhC'l coJc for a po(:ki:L-based digiial i;i>mniunica:ions sy?;lcni using a sell-syiichronizcd scramblei, \did method cnniprising the step^ oW determining Ihe puwer fnj of a bfi inier]i:&\''e parity jRlP-n} i:ode capable orJiscriminatint! beiwuun all error putierns uf a single IraniHii.'i.sion Lirrorafld replication.' thereof generated bv siiid -ielf-ivncltmni/Ljil ^iTumbier upon rcL^plJonoftran^niiiJcd FEC encoded frartK-s: determining the pnwiTofa poJ^iiomiaJ used to i^eniirEaii: n Hamming cod.;; of a [cnj,n:h oompaliblc wiMi (hi- packcl sizQ of riaid packet-based d]£J(al communicatinns sy3^-:ni: combining said BlP-n tudi.' ^nd said Hamming cod;: lu form said ftC code niid obtain, upon reception ul'snid iran&mitled FtC encifdcd Fnimei, a set of uiiiiiiJC svndromej; foi all cumbinaiionw of said single bit tran-smi^i^ion errors *ind rLpiications; and allowm^ ik: FEC code to correct all single n-an.qmjssion errors and rheir replications h> ihc stlf-t^^Tichronized scrambkr while prciiirvini; H bit iran^irion dea'iityof a pliy.sical layer ai provided by said sciainlileE
BRIEF DESCRIPTION OK THE DRAWINGS
i-ig I .sclieniaiicmly iiiusrrrtEC-s a jOGbL njedij ind^jpLLidLLiI phy-,LCal ]r.i':;rt'iicc
Fig. 2 depicts a flow Chan ofihiiL^ncodin^ and decoding algorithm according to a first
embodiment.
big. .i iicliemaiiealf^ illiiilratcs the concept of bit error spreading caused by a dcscramblmg opera! ion on a tingle data packet,
Fi^. 4 schematicd-llyilltistraies the concept of hit error spreading can.^edliy a dcserambling operation over multiple data packeLt; on a ^imglc channel.
big. 5 schcmaiieally illuslrnlcb multiple errors transmitted over a single link in a miiltklmk sysieni resulting in an uncorrectable error condition.
FL^ 6 d^jpiL^is a MOVL chail for 3. ~?:h>d ■?' lt^e■:^L[^; TEC puiynomiali: accordtny to a first embodimeni
hig. 7 shows an exemplar Tl-mrtrrix ofii "orivard oimr conection code accordini^ to a firsi
embodimeni uiing ai.;onil>iiiaiKin of bit-interleaved parity and H^unmnig onooding.
Hig ^ j^ho^vii a transposed ■version of tbc cxL^mplar H-matiix of Fig. 7 in sysiematic form
big. 9 illustrates a plot of the di-'^tribution ol tindcittled euons usine the for^^rd :;iTor correction encoding method according lo the first embodimeni
DET.VILED DESCRIPTION OF IHL FRLFEftRED EMBODIMFNTS
In the following dci^ilcd description of embodiments, rcfercnci: is madu io ihc accoinpanyinil drawings which form a part hereof, and in which are shown by way of illuilrrftion bipteilTc k:ml>ndimentslha.l are described in iuffidail detail to enable those skilled m the art to practice Ibe invention, and it is to be understood thai oilier ernbodimenis may be utilized and logical, >tructuraK ebtiiiica] and other chaoges may be m^de wiihoui d4:parti[ig frojn the si^opeofthc present invention.
Aeeordiny to a firr^t embodiment a FEC code is di.'^elosed that is compatible with the scrambler used by the 64B fi^B encodinjj; for cransmiNsion on SerOes channel links with a lower overhead (2/64 or 3%) than «B/10B encoding (2'8 or 25%). The FEC code according to Q first embodiment requires encoding and decoding to occur before scrambling and after dcfit^ianibliiig, respectively, so as lo prciicrve thepRtpcrtieiiOf the scrambling opi.Taiion on the iransmitJcd signal. T^lc proposed code afiowi Ihc eorrcction of any sing[e Tr^nimission error in spite of the tnuUiplicHlion by three of all tranj^miasiun errors resulting from the (i4B'66B descrambling process.
Fig. 2 depicts the encoding ^nd di;codiiig processing flow according lo a first embodiment A lo];iea| Xt)R is performed on the data word lo be transmitted to forni a 16 hit
hCC chsckhk sequence 2DQ in acatid^iice H'iJh ths ^quiti'ionfi ds^iined in ^sysitmatkH-
lO
niaJrifl The checkhiis ar^ appended [r> T'---.^i>i -LVOM to form ih^ i.Tn:oded dataword 2Q\. ^■hich 1.^ inpi;! lo ihe icrambl^-i Thu s.-r_T::Jed iar.^^.rJ is?hi:n iransiruried a^m^s the channel 202 dnd descraniblLd at ihe de^nnaiii-iri 203. The checsbiis dre '■op^rfW from the datawoiri and siored locaUy 2r syndrome from whicli ilie number ind location of eiitus i.^ del^nmned. TPk- firsi six bits of ihc syndiome correspond to (he BIP-n poilion ni'ihi.-encoding prote.s^ and reveal ih^-number of errors pr&^ent in the iiariMmllcd dal^word 20H. The reinainiriii Icn bil.s of [he error .syndrome wifl mdieuli- ihc location of one or more errors lo be corrected Si f.
RcfciTing to Jrig. J, vtirious orior ispreading syndrimioi. an- illusiriiicd for an individual packei in accaidan[:e wiih ifio applied tcrrtmblinij polynomial utilized iu rhc lAfl'bbfl proiooo^. For Ihe 6AB/66B proloeo^, the scr^mbVin^ poWTiomin^ is repiesenled ar., G(x) = J ■ X"^ ' X^'\ therefore the scrambting process Involves a multiplication by three of the daranord. A single error may occur any^^horc wiihm ilic packet trame, wlieiea-s iwo errorji (a dngleen-orand one replicated frvstancel maybe fip^ced il «EI interval ufO-^'Jbii^ dnyvvlierevvithinapackeloran mti^^■il of 39-5S bits anyv'here within the packet Thvi-.n cirors in fhi; packei AOuld he spaced ai intervai.s of 0, 39 and ^8 bixs. The crror.^ ibcrcfore span on 59 bits in accordance with the powers of ihoscraniblin@pol>Tiomial i.e.: 0. 39 and 5S. If no assumption is made a.^ to the number of ScrDcsUno^ (or hij^h-speed links) dedic^icd loiraasporlaframeprotectedby thefECcode, thena smi;le rranvmisMon eno] on a link may resuU in the occurrence an^'U'here in a frame of up To three errors Tfihrcc errois are within the same frame they are. however, assumed to be Jipaced in accordance with the p^iwcrs ofthe polynomial: U-J9'58. If [wo errors arc in the same frame they must be spaced wiihiii bii6 0-3'J or bJts y}-5)i any where in the frame. All these eumbmahons of errors, along with all single errors, have unique syndromes, and are therefore oonvctiiblc.
Fig. 4 shows muhiple data packets transmitted over a single serial link and illustiate.'i how a single bit error could produce a mu!ti-bii error depending on its bit location
in Ihe word Ifihc jingle bii ennr appears early in £hc n'''packet, then iht lull effect of the .scrambling can be seen. If ii occurs late in Ihe incident word, then part of rhe errors v,ould
fall oii(side the word. 'Hie -.-n-^r ii-:i!\bt-^'— i-l^'i-c "^ r^-fer to the relative bjf posirron wilhm ^nygj\enp£^ckeiorilLt spreaj ^'rror.s c^_-^J b> :n? scrambling pol>TH.irji[9J dunng the de.serjniJilinij process
hor cxanipli:, Bit Error Spreadi]!!; f shows the initial error occuninj^ in the middle of the n-l paoki:! ^nd is designated hy position 0. Aftei-pmce^MM^ by the descrambler. ih^-crmnsalfro spread to a bii position 39 bits lat^r m the SC<|IIL:IH:-. d.swcll ajiSS bii potilion^ lali'rin the r;eqNeni:;t Acoordinsly. Bit hiTor Spro^ding 1 results in the ivl paul^uL experiencing a double-bit error, whik ihc nlh packet exp^nence.s a Mjij^ic bit error. However, if (he initial ermr occur* a htlle Idier in the bilj^li earn, as shown in Bil Error Spread in ii 4. only Ihe inifinil error will be obsei-ved in ihi: [i-f packet, and the mtipacket ■A'III ^.v.pL:rience a double-bit orroi".
Bil Error Spreading 2 rihowj; an initial error oi\:LLrrinijiow^rd^ the beijinmng of the nlh pack^, and the rejiulting spread eirors also fall within the n"' packet, leading to a tnple-bii error.
Bit Error Spreading 3 is similar to Bit Error Spreading 4, but W'ilh the iniLial error occurring in ihe n' packet, and ihc resuliinj^ iproad ijirora tauiiny either ^ single or doublc-bii erioi i" the ii-l pjitkel, in addition to the .'-ingle or double-bit errors in the n'" packet.
Thu^i is can be seen that while a sinyk eiror correcting (SEC> Hamming code would be sufficient to correct a random single-bit error, it would not be able to correct either the double-bit errororthetriple-biterrorwhich are caused by The "icmmbling algorithm and ^hown in H11 three cases of Fig. 4
in [he case of a multiple channel liEik. Fig. 5 fttustralcs how -A single piickct ean be decomposed and transported on any number of links and reconstituted at ihe receiver Single, double arid triple bit errors can occur anywhere in packet and still be conected because the ripQcing of replicated errors is a Tunciion ofihc scrambling polynnmial. if the BIP-n code exponent is chosen such that there are unique remainders modulo n. then ihc replicated bit errors can be identified and corrected.
\9.
As sfujVhn in Figure ;"."-'-' 7 ' - - "^pOi'^Ll inio 4 ^.ab-pact els. £^di sub^ pack';! IS .-icrdiTibfed ami Jcscran-.ijieG maivi.-LUj.iv. Hawevi^r. iMf-- ii ■jaii be SL-CM that ihi: ^ipleJil i occurriim in MiL'-p^cfcer ^ c^]^-,t.-. Iwo errcjr^ in the n' pacftci. p[us an arfdiT ioriHf snor in (fie n-f packe" '."nfortunaicfv, ECT infomiaiiori i^ rn:ff propaTLmed aLni.si^ ji'a*:kc( boundaut^. 4ci.'iiiditi^fy. ih? mui'ipMcacion of a sinj^re bit errnr 10 (he n+f pack'.-i I'nrhe
If p^i-kei:^ are Iridnremitted over a sulTicicnt niLml>erof liiikii so ihat each (.-ornponeni ot'tht: iraLfimLtiiirt data p^nj^ei is ittiiiUci- ihan lObitSsihtu onlv single ■;^^or^ would have to be corri^cied and ;iiiy rimj^lt; Hai-nmini! code impleinentannii would suffice This is b^'ijause n icplicaitd error lAould never fall wnhin ihe same i^ub-patl^ci in which ihe shiulc bit emu uppeared Por exaiTip[e. LA a 64E;'^6B t'uiie. 6'T-byi? trarncstan be pmiected ^vnh 2 byi^.s of ECbit mimrnum bpraidmi? liL^tarice of fhe aisrambthg [K-iiynomifil Ihas w^^ae^'er ^n errori^tri^ur?. it irFaW nevcf be sprcdd to fwi^t^ne £Cr H'j>fd, jijjd ±crcFoTi^\ no moyc th^n 3 s??fgJc bi? cffor OCQUT^ in c^ciiofthc nffccicd packcis. How{;vj?r. toJ^^ud of appi'oacJ: ii iueffkicn' bscaii^L- nf ihe ^iddinomti h^nd-^^idib required in implejrenL .More often, mi]]lipJebiilfli]psinyroijp,s of A.hor ](< are u.sed to improve bjinowiditi In yenemi, il N^D '- ^. men iir^jinpii- r-i.iinjiiijii^ v.\>ijc j_^ .MjijjvK-^iL "ih.:iv ^^yain. K IS Ihe total length of the ECC prolect?d frame in birs, b is the number of biTlants, and s 1^ th^ minimum spreading dislance of ihe scrsmhlerpol.vnonvial
An LCC sdieme is designed (0 maich an eiror model. Therefore, any error complying with the crior model tnuRt be corrcoLahle. The etror model described herein is a single transmifusion errormuUiphed by the descramblmg pmce.ssso that replicated errors spaced according to the po^^'e^s of the scrambling polynomial muit be considered. However, the abiliiy of an ECC code in detect additional errors, m this ease a double bit error, should be assessed For o.amplc, 'A'licn T^O iransmi^ion ciroi-a occur, up to six errors may be dijiecicd dfici dcscramhimg, Iiei-ahvc birnulation is nccco^ary [g a&scss the level of detcclion
lb
caji£Lhjf[i> of (he tEV ccitk- !dea||v. uie ^r^ -MQ^: inould achie\c H ib^le erroi LorreclbndoNhIt'error dek-ciioii^FC VET. :e^ e'o:-ihiiMTK-i^, bui ihis may ii„i be redlr:;ed id piucittv 'A here a smjiJI pLTei:nid^e of double irariMnLssion errors Lire noi ikiLLred.
Theff4aTi6R ^(andand defines packois uf 64 bits [O v^ineh two hiii jnre ^dded for dehnealinn.Thi: invention implicijly ayaumes (hjtprotoclion wjih an FCC will be carried on liirycr packclJi or tVamc.s su 1 he redundant biCri nccdsrf lo iTTiplcrncni ECC. v^iil ^t^y aLa fcasoniihJe Jev<;| As an exempJar>- ca^e, framiiS, intkidin^ redundant bit:i. are ]e.:)ri£'itd lo an enure mulliple of ihosc (i4-bn packeis Tho FEC eode described herein need inn M^'.ume jny particular method to deiiiieiik- jinECC protected frame. J he FhC code ol'ii Hn-ii embodiment can pj 010^:1 a datawordof Up lo 2"'-l - 1,0?'^ hh-i Thwi. in practice- ECC protected frames (including 16 redundant bilsj comprism;; up (o fifteen 64-bit packets, e.g., of the rypc defined by the ('i4B.T/>B tiand'ird, may be considcrcdr
A code to reah^ehtC] with rohiisi error dLiociion Jind ;:jrTei;|[on eapabihty according to a fiii^t emlnidinicni ii s(rtn;lurcd di diicutitbed below. The FEC eode combines a Hamminji eode wiih a Dii TnterJeaved Parity of degree n (BTP-n) code, which can be gtTieT?i\&d'J'Vih\h.'e t'iVC>A£i'm]Wly^timia^ X'' + \ The Hav^^mi^^ todt ca^"^ Vv^ ^t\\i\"fl.^id '.'Ki%m any irrL^diK'ible pt>lynomifil, prcfcrjbiy primitive, a list of which can be found, in "Error-Correcting Codes', Peterson &. Weldon, The MIT Press, 1972, which is incorporated herein by reference. Peterson and Weldon illustrate a 10''' order polynomial in Table C,2 of app:;r-d,-^r. ;-cp^c■.c^lcd-^'201V!:nct^!1n^Jtionie: Hf-^ = V" + X'- l A ^V" r,rH^ RTP code is i:hoscn. for reations explaindd infra, and toTTCSponds lo ilie rollo\^ing polynoinia! B(?L) = X'' I J.
The degree of the Hamming code determine!* the length of ihcoodo. 11;.. rhc maximum packet or code word size, including ihe ECC bits that can be protected, A de^ree-10 primilivc polynomial, whiuh genciaies a maximum lengtli sequence, can span over \.023 bits. Thus, it can be used lo prolcci a lypiijal 64-byit: packet and any length up lo 127-byle packets. The degree of the DIP is chosen to ensure uniform irrur spacing as dciined by the scrambling polynomijil term*;: 0-39, ^9-58 (i.e.: 19 bits apart) and 0-^8 do not have the same icmaindcis, modulo n. This appioach ensures a unique checkbit error syndrome, which is the rcsLiJi oTsn XOR opi:raiion beiu'i;en ihc Originally iraiL^inincd dataword and ihc
Iff-
iL.Tonsl[nj[;ddjmword^J(hf d;^;-^:ja.- --■::.- F Mb.^ ^B'MB siandjtd, Lh;; RIP-n code musl beai loasi H ^iuh older for Lh^ chcix,- >.T;ir.ri;: polynomial <^(X>- X"^^ x'" I becaiisL /ts .shown [n iible I bHuv^'. n = ft [^ the fitMmodiih-i ihai prov[de,s different remainder.^ fiirall ]>owtr» of the scrambler pol>nomiirl leraii:
(0 10 ?<') 58) modulo.] - - (0 1 0 1)
(0 19 :^9 58) modulo 4 = = (0 ?, 3 2]
(0 19 V) 5^1 raudiflo ; - = (0 4 4 3)
(0 (') V) Ti^} moduio Hi = = (0 I .J 4}
to 19 .19 ^^) modulu7 = - (0 ^ ^ 2]
1Ahlc I
Fij;, 6 depicts a flow chait showing an algiirilKm ibr soleofini^ fho order of the Hamming code and the BIP-n code, .^ueh ihai ihe moil robiial tolution it, realized for the «idih and number of tihanncb utilized by the system. The distances between each possible set of multiplied bit errors niuM be deiermined from the powers of the scramblm^ pol^Tiomial 600, wbieh in the ca.'^e nflhc[i4R/66R slaiidaid eorres|>f]nd.s to (i(Xk~ X -i- X"'" -I- 1 The minimum power (n) of a bit interleave parity (BTP-n) eode muoi bo doi:"nnined^ such that any single transmission error pattern and its replications remm a unique modulo n remairidi;r (601-605). For fhe Hamiiiing code H(x) - X^^-^X^+ 1, choosing n = e for BTP-n results in combinations of errors ipaecd as : 0-39. 39-5^. 0-39-5X, with single errors always returning a different pattern for the 6-bil component oftho syndrome eonespondingio the HIP-n as sliouii below in lanle J. ivioduio n division of LIIL bu UL-.LQII'-L^ i.-. 1.1 J^ i'jj.-.i valu; ^f Q to provide unique remainders. Based on die total number of bits that maybe dedicaied in ECC checkbits for a given system eonfigurai ion. the degree ofthe Hamming code mis calculated as ni n bits 607. Choosing a BIP-6 polynomial allows the maximum number of cheokbiti to be dedicated forihc second pan of The code, which ensures rhat the higlie&t level of robustness for protection a^Hinsr multibii eiTors.
DIP'S syndrome pattern ^and any rotation thereof):
0 12 3 4 5
flingle error 10 0 0 0 0
0- 19 J 1 0 0 0 0
0-i9 10 0 10 0
0-39-58 1 1 0 0 1 0
Table :
15
Accordiniili, uheii i:orz1--\-::i - ' 3!^-S ;3le. a .^[mpl: blicnmuig ttid.:: 'y sufficieni in adfic-ve a sing[s ?jrnr .■omfc:.-_^ coa= m ^mk" Liflh;: error multiphc^i ion inimdiiccd by [he ^crtiniblcT jinyinhere Ja i fruiii^ ami pLiti?nridlly trLinji]-io[ii;d L.U\T severaJ links. In ihis rcgflrd. all error combinai ions rnaichirii^ The error Lnodel have it unique syndrome which is easily decodablc >md correciable.
Rurumngtorig. ?. thcH-infliji>L Tonnf 1.023 columns. Id lOws) tH'Jh:; (1.023.'l .0071 code ^en^rak'd from ihe mutliphtalion ofthe daLa^*'i>rd wiihHfxi diid BIA) dccordingto n nr.sl i;mbodiment is shou'n. Howe\'er. lo aWo^'- a .slrai^hifbrrt'drd computarion ofiho ECC bilrt di encoding, Ihe matnx .^hov^rj m Fij^. 5 should preferably be rran-iposed lo a syslematie form which i-eqmrcs a diwjiunalizfllion of ihecheckbitmamx. I his can be accompli^liod iibiinjj tl^ndsrd mathematleal mcihod^. The rcsuliiriR s>slcrrijiiic Ibrrn mutrix dijrivcd from Fig, 7 is shown in hig. K
After checking all combinations of single tn Inple hii erroi-s, r^paced is .shouii m pjgji. .1 and 4, the FEC code provide?' a robusl sin^li: i;rTur k'orn:(;ri[in i;odt i" tpilo of iht miihiplii:nlionoferrori by the scrambler polynomial. In a |.0?>bir packet there are 5.976 combinaiions of errors, each remming a different s>-ndTome so they ad can be unamhiguoiisly correcied. The iiuml^cr of unique error syndiomc*; fnr each class ot error are as fulluw-i:
3-bii error combination's 5S-39-0 = 965
2-bil error combinaiions 59-0 = 9^4
2-bii ^tror combinaiions 5^-30 = 1,004
[-bii error combinatiorm = K023
Total: 3.976
For a dalK field shorter than ihe capaciiy of ihe matrix, the FEC code must be depopulated lo match the actual application pa^;ke( size and ihe discarded bits are not considered. To preserve ihe propeny of the matrix the dt.T>opulaiion nmsi occur exhaustively iTom left 10 nghi, down to the si2e of the packet.
ft
Decoding ai ili;-dcsUi^i:..!:. ^- .. ^,-v. ,-: ::.-:d iiibsequem in ihc de>crani]iliri^ opi^rrftion. I IK .sysieniatic fnrii ^''sbe M-ms'i-iy ,L hj^'ii ha..^ ths ■;arrit properlie'' a^ i\K-orii^inal nidlrix, should bi: used lo sL'npiitS I'lj r^LJ^nerjEion ol'ECC bi!':. HOW:^V,T. (his complicates the dci-'odm^ of ihe ek'fds a reii tyndrome vector by the square i;h;vk bit matrjM :ihown in Tiible 3 below,
15 n
OOOO1000001OOOOO 15
00000lOOOOOi0000 I
1000001000001000 I
01oonooi00000100
(H)ionoooioooooio i
000lOooooToonooi j
000000looooonoon |
]ODOOtJ01000000DO 1
OlOOOOOOl0000000 I
0010000001 (X)0000 I
100lOOOOOO100000 I
01[H)1QOOOOO 10000 |
ooiooiooonooiooo |
OOCIOCOOOOOOOlOtf ■
0000100000000010 ■
00000 lOOOOOOOOOl 0 Tflbk3
hor example, if we iS^ume that biLsalindic&s 1,U1M & y9i'[l9-bii!i apail) are m eiror, ilio Byiidroiiit rcmmod by (hi: b>itL;malii: mafrb; iii
Of)! 0^ noioi 00000
After transformation usmg The square matrix of Table 3 the syndrome becomes:
OllOOOiOllllOOll- which is indeed Ihe syndrome Ihm woulJ bi: r<:iumi?d by ihc non-systematic matrix above for the original data stncam.
17
The flrii {lefi-mo.'iTt (^ bi'? a.-? the --_■>-—-T.i-orri of ihi,- BIP generated oomponeni andai-2 indiLdiivcofa 2-bil error :^\[y:-.-' ^^ [r.^.c.ij ID (he BlP-6 s>FHlrorne panenn.>r rabl.' 2
An alternate incijiod is to use tlie sysiLjmarrc form maJii>L Rir j^eneraTion and ihi? original (non-.^ysili;:l (i i: errors resuhing fmm a smglobil tian.smiwion error and jipaccd as iho power of the scrambbr) and caiinoi b;- coiTi^ctcd,
Mariyof Ihe transmission errori^thal fail lo corroapondto fhe error model can nc\LTtheless be detected because, as dis^^usscd above, only 3,97fi syndromes arc used for error coneci ion oiii of 2"'-! = 65,i35 possible error syndromes md]i^aiod by ^ 16-bit .flyridR>rnc Such errors can be the result of moic ihan a sinj^le trror occurriiijj in the same pjckel on the serial links. "I'hus. foi cxampli::. up ro 6 orrori^s aflcr ^cTrtmblin^;. could be present in a ■single packcl ss aresuli of a double traiLsmisMOTi error. Fi^^. 9 shov-sihc siaiisiicdl distribution of a Monte-Carlo simulation plotting the results fotind foi l>etween 2 to 6 errors not matching the error model - approximately 91% of which are dciccicd. However, [he remjnmnyy%Tidn>mei
Iff
■^"hil^ Ihe iiui;n11onl'.a.s re^n GLr^c^iijeo "im refi^rvtiLc LO g prefeiieil ornbodiinciit nr .jmbodiments, iJ 'AIJI b^ uidsrstUiA] '?■- :ho>. i..JL\-: -n .i:= ^n thai vaiioii^ I'hani^es may he made jind i^quivaleni^ irijiy he ^ubsinuied fur uioment: ihereof \vitlii-nii d^'fidrtmii from tlii-ftcope of the invcntjon In addition, niany modi-ficatioa'' may lio m^d? to adapt a paftiailiir iituatiOLi or ififeridl to Ihe Tjachiny^oflhe tnvsnlion withihtpi difparting fi-C»m th^:: :'^s.'ii.'nli^] si:opi.' 'hereof. Therefore, il i^ intended thiit Die mvuniion noi be linmed ui fbf p^rlioular embodiment disobicd ^s Ihcbe^t modL: OL>iil;:mplated forcanyingnuttfiit inv?ni(on. tmiihal rlr invenllon will rncUirt^ a\\ (:inboiimenls falling VMTIILII Ihi: ^t^?pe of Ihe appenrti:{l d^n^.
\«f
I A method of sjeneraiinj a f-TA ^rd::- " :oi'---i";n iFECi code fora fiiickei-
based digital LumiTiunicaiion?^ s>st^m. ihi- meihod compri^ii-i(?: appKuig -1 firil Lncoding aJcorithin m a lir^[ dalav^ord:
sppl>ing a second encoding ali'oriihm to the firstdataword:
genei ariiig a ITril chcckbil sequence for the first dalaword;
appending the checkl>ii sequence lo IIIL- lir^l JaEaword;
scramhlrrig the flrsl dala^vurd al a source node:
Iransiniltin^ [he firstdataword on a data transinision link Iroin UK- sourn: nod^ [0 a desiinalion nodi::
descraiiihling The rran^millLjd lir^l dalav^ord aL the destination node:
j^enerating a second checkbit sequence based on the transmitted daiav\ord:
comparing the first checkhit ^hequence with the second checkbit sequence:
delermining whi^lhcr ihe rcccivi;d dala^\ord contains a llrM bit i^rror: and
correcting the first bil eror and a firsl and st^cund Ts:plii:3k'd bil trmr.
2. The method according to claim I. further comprising representing a p[iira[ily uf cnc^T'ded d:3T::'-'.':^rd'' in a fif^t m^tri^. '''hereby? ? nlnr^li'v' offhtTLbii ^■riucnc'cs corresponding lo each of the plurality of datai^ords is appended to the first matrix.
3. The method according to claim I further comprising appending a checkhit i^equence to each of a corresponding pluralil> of enctjdcd daiawords.
4. The mcihod according to claim I, further comprising concattnaling a plurality of daiawords and providing a single checkbit sequence: for error correction.
!i. The method according to claim 1. wherein the data transmiision link conipiises
a multiple link coinmunicalions channel capable of inverse multiplexing
^V
Documents
Application Documents
| # | Name | Date |
|---|---|---|
| 1 | 3135-chenp-2009 pct.pdf | 2011-09-04 |
| 2 | 3135-chenp-2009 form-5.pdf | 2011-09-04 |
| 3 | 3135-chenp-2009 form-3.pdf | 2011-09-04 |
| 4 | 3135-chenp-2009 form-18.pdf | 2011-09-04 |
| 5 | 3135-chenp-2009 form-1.pdf | 2011-09-04 |
| 6 | 3135-chenp-2009 drawings.pdf | 2011-09-04 |
| 7 | 3135-chenp-2009 description(complete).pdf | 2011-09-04 |
| 8 | 3135-chenp-2009 correspondance others.pdf | 2011-09-04 |
| 9 | 3135-chenp-2009 claims.pdf | 2011-09-04 |
| 10 | 3135-chenp-2009 abstract.pdf | 2011-09-04 |
| 11 | Other Patent Document [27-09-2016(online)].pdf | 2016-09-27 |
| 12 | 3135-CHENP-2009-FER.pdf | 2016-11-15 |
| 13 | Petition Under Rule 137 [12-05-2017(online)].pdf | 2017-05-12 |
| 14 | Other Patent Document [12-05-2017(online)].pdf | 2017-05-12 |
| 15 | Other Document [12-05-2017(online)].pdf | 2017-05-12 |
| 16 | Form 3 [12-05-2017(online)].pdf | 2017-05-12 |
| 17 | Form 26 [12-05-2017(online)].pdf | 2017-05-12 |
| 18 | Examination Report Reply Recieved [12-05-2017(online)].pdf | 2017-05-12 |
| 19 | Drawing [12-05-2017(online)].pdf | 2017-05-12 |
| 20 | Description(Complete) [12-05-2017(online)].pdf_303.pdf | 2017-05-12 |
| 21 | Description(Complete) [12-05-2017(online)].pdf | 2017-05-12 |
| 22 | Claims [12-05-2017(online)].pdf | 2017-05-12 |
| 23 | Abstract [12-05-2017(online)].pdf | 2017-05-12 |
| 24 | 3135-CHENP-2009-HearingNoticeLetter.pdf | 2018-04-11 |
| 25 | 3135-CHENP-2009-Correspondence to notify the Controller (Mandatory) [09-05-2018(online)].pdf | 2018-05-09 |
Search Strategy
| 1 | search_03-11-2016.pdf |