SE512145C2 - Device for correction of burst and random errors - Google Patents

Device for correction of burst and random errors

Info

Publication number
SE512145C2
SE512145C2 SE8904169A SE8904169A SE512145C2 SE 512145 C2 SE512145 C2 SE 512145C2 SE 8904169 A SE8904169 A SE 8904169A SE 8904169 A SE8904169 A SE 8904169A SE 512145 C2 SE512145 C2 SE 512145C2
Authority
SE
Sweden
Prior art keywords
circuit
error
unit
burst
correction
Prior art date
Application number
SE8904169A
Other languages
Swedish (sv)
Other versions
SE8904169D0 (en
SE8904169L (en
Inventor
Atsuhiro Yamagishi
Touru Inoue
Tokumichi Murakami
Kohtaro Asai
Original Assignee
Mitsubishi Electric Corp
Priority date (The priority date is an assumption and is not a legal conclusion. Google has not performed a legal analysis and makes no representation as to the accuracy of the date listed.)
Filing date
Publication date
Application filed by Mitsubishi Electric Corp filed Critical Mitsubishi Electric Corp
Publication of SE8904169D0 publication Critical patent/SE8904169D0/en
Publication of SE8904169L publication Critical patent/SE8904169L/en
Publication of SE512145C2 publication Critical patent/SE512145C2/en

Links

Classifications

    • H—ELECTRICITY
    • H03—ELECTRONIC CIRCUITRY
    • H03M—CODING; DECODING; CODE CONVERSION IN GENERAL
    • H03M13/00—Coding, decoding or code conversion, for error detection or error correction; Coding theory basic assumptions; Coding bounds; Error probability evaluation methods; Channel models; Simulation or testing of codes
    • H03M13/03—Error detection or forward error correction by redundancy in data representation, i.e. code words containing more digits than the source words
    • H03M13/05—Error detection or forward error correction by redundancy in data representation, i.e. code words containing more digits than the source words using block codes, i.e. a predetermined number of check bits joined to a predetermined number of information bits
    • H03M13/13—Linear codes
    • H03M13/17—Burst error correction, e.g. error trapping, Fire codes
    • H—ELECTRICITY
    • H03—ELECTRONIC CIRCUITRY
    • H03M—CODING; DECODING; CODE CONVERSION IN GENERAL
    • H03M13/00—Coding, decoding or code conversion, for error detection or error correction; Coding theory basic assumptions; Coding bounds; Error probability evaluation methods; Channel models; Simulation or testing of codes

Landscapes

  • Physics & Mathematics (AREA)
  • Probability & Statistics with Applications (AREA)
  • Engineering & Computer Science (AREA)
  • Theoretical Computer Science (AREA)
  • Error Detection And Correction (AREA)
  • Detection And Prevention Of Errors In Transmission (AREA)

Abstract

The apparatus includes a circuit (2) for generating two n-bit syndromes corresponding to the received signal, a circuit (4) for converting the two n-bit syndromes to a 2n-bit syndrome, a random error correcting circuit (7), a burst error correcting circuit (5), two combining circuits (11a, 11b) and output selecting circuit (6). The circuit (7) inputs the two n-bit syndromes and outputs a random error correction signal to one of the combining circuits (11a) and the circuit (5) inputs the 2n-bit syndrome and outputs a burst error correction signal to the other of the combining circuits (11b). The combining circuits combine the correction signals to the received BCH code signal. The output selecting circuit (6) selectively outputs one of the combined signals in accordance with the decoding conditions of the error correcting circuits (5, 7) and the result of comparison between the decoded and error-corrected signals.

Description

512 145 2 de koden, men inget definitivt förslag föreligger vad gäller hur tillståndet pá kommunikationsbanan skall greppas på ett konkret sätt och vidare finns inget kriterium på hur ett sådant tillstànd skall bedömas på lämpligt sätt, varför det är svårt att noggrant styra den väljande kretsen 6. Ytterligare ett problem är att det är nödvändigt att respektive enheter oberoende av varandra inkluderar syndromgenererande kretsar för extrahering av feltillstándet eftersom den skurfelkorrigerande enheten och den slumpfelkorrigerande enheten är anordnade oberoende av varandra. 512 145 2 the code, but no definitive proposal exists as to how the state of the communication path should be grasped in a concrete manner and furthermore there is no criterion as to how such a state should be judged in an appropriate manner, which is why it is difficult to accurately control the selecting circuit 6. Another problem is that it is necessary for the respective units to independently include syndrome generating circuits for extracting the error state since the burst error correcting unit and the random error correcting unit are arranged independently of each other.

Föreliggande uppfinning syftar till att lösa sådana problem som beskrivits ovan och att åstadkomma en anordning för avkodning av en BCH-kodad signal och för korrigering av ett komplext eller sammansatt fel i den BCH-kodade signalen, vilken anordning är kapabel att fastställa kommunikationsbanans tillstànd, att konkret tillhandahålla ett kriterium för bedömning av kommunika- tionsbanans tillstànd och att gemensamt använda en syndrom- genereringskrets för en skurfelkorrrigerande enhet och en slumpfelkorrigerande enhet.The present invention aims to solve such problems as described above and to provide an apparatus for decoding a BCH-coded signal and for correcting a complex or compound error in the BCH-coded signal, which apparatus is capable of determining the state of the communication path, concretely providing a criterion for judging the state of the communication path, and jointly using a syndrome generation circuit for a burst error correcting unit and a random error correcting unit.

Detta syftemål uppnås genom en anordning för avkodning av en BCH- kod använd för korrigering av en komplex signal, vilken anordning är kapabel att fastställa kommunikationsbanans tillstànd genom användning av det avkodade resultatet från en skurfelkorrigerande enhet med en skurlåsningsfunktion samt det avkodade resultatet frán den slumpfelkorrigerande enheten, varvid anordningen uppvisar en krets för bestämning av resultatet av en operation med en krets för bildande av en operation av heltal med modulo 2"-l, varigenom konkret tillhandahàlles ett kriterium för bedömning av kommunikationsbanans tillstànd för styrning av en utsignalväljande krets, samt varvid vidare ett organ för omvandling av ett syndrom är anordnat, varigenom den gemensamma användningen av en syndromgenererande krets kan uppnås.This object is achieved by a device for decoding a BCH code used for correcting a complex signal, which device is capable of determining the state of the communication path by using the decoded result of a burst error correcting unit with a burst locking function and the decoded result of the random error correcting unit, the device having a circuit for determining the result of an operation with a circuit for forming an integer operation with modulo 2"-1, thereby concretely providing a criterion for judging the state of the communication path for controlling an output signal selecting circuit, and further wherein a means for converting a syndrome is provided, whereby the common use of a syndrome generating circuit can be achieved.

I den bifogade ritningen visar: 512 1.45 3 Fig. 1 ett blockschema som illustrerar en konventionell anordning för avkodning av en BCH-kod med en korrige- ringsfunktion för ett komplext fel; Fig. 2 ett blockschema illustrerande en anordning' för av- kodning av en BCH-kod med en korrigeringsfunktion för ett komplext fel i enlighet med denna uppfinning; Fig. 3 ett blockschema illustrerande detaljer av den slump- felkorrigerande kretsen i fig. 2; Fig. 4 ett detaljerat schema av den skurfelkorrigerande kretsen i fig. 2; Fig. 5 ett detaljerat schema av den utsignalväljande kretsen i fig. 2; och Fig. 6 en tabell som visar kriteriet för styrning av den utsignalvälj ande omkopplaren som ingår i den utsignal- väljande styrkretsen i fig. 5.In the accompanying drawings: 512 1.45 3 Fig. 1 is a block diagram illustrating a conventional apparatus for decoding a BCH code with a correction function for a complex error; Fig. 2 is a block diagram illustrating an apparatus for decoding a BCH code with a correction function for a complex error in accordance with this invention; Fig. 3 is a block diagram illustrating details of the random error correcting circuit in Fig. 2; Fig. 4 is a detailed diagram of the burst error correcting circuit in Fig. 2; Fig. 5 is a detailed diagram of the output signal selecting circuit in Fig. 2; and Fig. 6 is a table showing the criterion for controlling the output signal selecting switch included in the output signal selecting control circuit in Fig. 5.

En utföringsform av föreliggande uppfinning kommer nu att beskrivas. I fig. 2 visas i blockschemaform en felkorrigerande enhet. I ritningen betecknar hänvisningssiffran 1 en ingàngster- minal för inmatning av ett mottaget kodat meddelande, 2 en syndromgenereringskrets för generering av två syndrom om n bitar för korrigering av ett slumpfel, 3 en fördröjningskrets för kvarhállning av det mottagna meddelandet under perioden för generering av syndromen och korrigering av ett fel, 4 en syndromomvandlingskrets för utförande av en omvandling fràn de tvà syndromen om n bitar genererade i syndromgenereringskretsen 2 till ett syndrom om två n bitar för en skurfellásningskrets för korrigering av en skurfelkorrigering, 5 en skurfelkorrigerings- krets för beräkning av den position i vilken ett skurfel genereras samt mönstret av skurfelet, 6 en utsignalväljande krets uppvisande ett kriterium för fastställande och bedömning av tillståndet pá en kommunikationsbana genom användande av de 512 145 4 avkodade resultaten från den skurfelkorrigerande kretsen 5 och en slumpfelkorrigerande krets nämnd nedan, 7 en slumpfelkorrige- rande krets för mottagning av syndromet såsom en insignal, vilken är en vektor uttryckt genom polynombasen i ett finit fält och erhålles med syndromgenereringskretsen 2, för omvandling av det såsom vektor uttryckta syndromet till ett exponentiellt uttryck av ett primitivt element i det finita fältet, för erhållande av ett felpositionspolynom genom normalisering av det omvandlade exponentiella uttrycket med en heltalsoperation av modulo 2"-1, för erhållande av radikalen av det normaliserade felpositions- polynomet genom uppslagning i en tabell av den normaliserade felposition som beräknats i förväg för de konstanta termerna i det normaliserade felpositionspolynomet, för beräkning av den sanna felpositionen ur den normaliserade felpositionen samt för korrigering av slumpfelet, 8 ett data-ROM för lagring av data för omvandling av syndromet uttryckt som vektor i polynombasen i det finita fältet och som erhållits från syndromgenereringskretsen 2 till det exgonentiella uttrycket av det primitiva elementet i det finita fältet och data för den normaliserade felpositionen som är radikalen av det normaliserade felpositionspolynomet, 9 en utgångsterminal för utmatning av de avkodade resultaten, 10 en terminal för utmatning av en signal när ett okorrigerbart fel som visar det slutliga avkodade tillståndet detekteras, och 11-a och ll-b exklusiva ELLER-kretsar för addering av felkorrektions- pulser utmatade från den skurfelkorrigerande kretsen 5 och den slumpfelkorrigerande kretsen 7 för det mottagna meddelandet.An embodiment of the present invention will now be described. In Fig. 2, an error correcting unit is shown in block diagram form. In the drawing, reference numeral 1 denotes an input terminal for inputting a received coded message, 2 a syndrome generation circuit for generating two syndromes of n bits for correcting a random error, 3 a delay circuit for holding the received message during the period for generating the syndrome and correcting an error, 4 a syndrome conversion circuit for performing a conversion from the two syndromes of n bits generated in the syndrome generation circuit 2 to a syndrome of two n bits for a burst error locking circuit for correcting a burst error correction, 5 a burst error correction circuit for calculating the position at which a burst error is generated and the pattern of the burst error, 6 an output signal selection circuit having a criterion for determining and judging the state of a communication path by using the decoded results from the burst error correction circuit 5, and a random error correcting circuit mentioned below, 7 a random error correcting circuit for receiving the syndrome as an input signal, which is a vector expressed by the polynomial basis in a finite field and obtained by the syndrome generation circuit 2, for converting the syndrome expressed as a vector into an exponential expression of a primitive element in the finite field, for obtaining an error position polynomial by normalizing the converted exponential expression with an integer operation of modulo 2"-1, for obtaining the radical of the normalized error position polynomial by looking up in a table the normalized error position calculated in advance for the constant terms in the normalized error position polynomial, for calculating the true error position from the normalized error position and for correcting the random error, 8 a data ROM for storing data for converting the syndrome expressed as a vector in the polynomial basis in the finite field and obtained from the syndrome generating circuit 2 to the exponential expression of the primitive element of the finite field and the data of the normalized error position which is the radical of the normalized error position polynomial, 9 an output terminal for outputting the decoded results, 10 a terminal for outputting a signal when an uncorrectable error indicating the final decoded state is detected, and 11-a and 11-b exclusive OR circuits for adding error correction pulses output from the burst error correcting circuit 5 and the random error correcting circuit 7 for the received message.

Fig. 3 visar detaljerna av den slumpfelkorrigerande kretsen 7 som visas i fig. 2, och i denna figur avser hänvisningssiffran 12 en ingångsterminal för inmatning av syndromet uttryckt som vektor i polynombasen i det finita fältet och som erhållits genom den syndromgenererande kretsen 2 i fig. 2, 13 register för att hålla insignalsyndromet, 14 en adderingskrets med modulo 2"-1, 15 en komplementär sifferkrets med modulo 2"-1, 16 ett register för att temporärt hålla data, 17 ett register med en funktion för att kontrollera resultaten från beräkningen av adderingskretsen 14 med modulo 2"-1 och den komplementära sifferkretsen 15 med modulo 512 2145 5 2"-1, 18 en räknarkrets för beräkning av den sanna felpositionen, 19 en ELLER-krets för blandning av korrektionspulserna som utmatas fràn räknarkretsarna 18 och 18, 20 en adresstyrkrets för utmatning av en adress till data-ROM 8 som lagrar data för omvandling av syndromet uttryckt sàsom vektor i polynombasen i det finita fältet till det exponentiella uttrycket av det primitiva elementet i det finita fältet samt data för den normaliserade felposition som är en radikal av det normaliserade felpositionspolynomet, 21 en adressterminal för utmatning av en adress till nämnda data-ROM 8, 22 en datainmatningsterminal till vilken data inmatas från nämnda data-ROM 8, 23 en utgàngsterminal för' utmatning av' korrektionspulsen, och 24 en terminal för utmatning av en detekteringssignal för okorrigerbart fel vid ett fel som ej kan korrigeras vid den slumpfelkorrigerande kretsen 7.Fig. 3 shows the details of the random error correcting circuit 7 shown in Fig. 2, and in this figure, reference numeral 12 denotes an input terminal for inputting the syndrome expressed as a vector in the polynomial basis in the finite field and obtained by the syndrome generating circuit 2 in Fig. 2, 13 register for holding the input signal syndrome, 14 an adder circuit with modulo 2"-1, 15 a complementary digit circuit with modulo 2"-1, 16 a register for temporarily holding data, 17 a register with a function for checking the results of the calculation of the adder circuit 14 with modulo 2"-1 and the complementary digit circuit 15 with modulo 512 2145 5 2"-1, 18 a counter circuit for calculating the true error position, 19 an OR circuit for mixing the correction pulses output from the counter circuits 18 and 18, 20 an address control circuit for outputting an address to the data ROM 8 which stores data for converting the syndrome expressed as a vector in the polynomial base of the finite field to the exponential expression of the primitive element of the finite field and data for the normalized error position which is a radical of the normalized error position polynomial, 21 an address terminal for outputting an address to said data ROM 8, 22 a data input terminal to which data is input from said data ROM 8, 23 an output terminal for outputting the correction pulse, and 24 a terminal for outputting an uncorrectable error detection signal in the event of an error that cannot be corrected at the random error correcting circuit 7.

Fig. 4 visar detaljerna av den skurfelkorrigerande kretsen 5 i fig. 2, varvid hänvisningssiffran 25 är ingángsterminalen för inmatning av utsignalen från syndromomvandlingskretsen 4 i fig. 2, 26 är en 1-bits fördröjningskrets, 27 är en omkopplare för styrning av en áterkopplingskrets bestående av fördröjnings- kretsar 26 anslutna i slinga genom omkopplaren, 28 är en väljaromkopplare för val av antingen utsignalen från syndromom- vandlingskretsen 4 eller data frán áterkopplingskretsen, 29 är en làskrets (noll-detektering) för detektering av det faktum att de övre 2n-b bitarna av det linjära àterkopplingsskiftregistret eller àterkopplingskretsen med en längd om 2n bitar blir noll, 30 är en terminal som utmatar en okorrigerbar skurfeldetekte- ringssignal när ett fel detekteras som ej kan korrigeras vid den skurfelkorrigerande kretsen 5, och 31 är en felmönsterutgàngster- minal för seriell utmatning av ett felmönster som skall korrige- ras när skurfelet korrigeras.Fig. 4 shows the details of the burst error correcting circuit 5 of Fig. 2, wherein reference numeral 25 is the input terminal for inputting the output signal from the syndrome conversion circuit 4 of Fig. 2, 26 is a 1-bit delay circuit, 27 is a switch for controlling a feedback circuit consisting of delay circuits 26 connected in a loop through the switch, 28 is a selector switch for selecting either the output signal from the syndrome conversion circuit 4 or the data from the feedback circuit, 29 is a latch circuit (zero detection) for detecting the fact that the upper 2n-b bits of the linear feedback shift register or the feedback circuit with a length of 2n bits become zero, 30 is a terminal that outputs an uncorrectable burst error detection signal when an error is detected that cannot be corrected by the burst error correcting circuit 5, and 31 is an error pattern output terminal for serially outputting an error pattern to be corrected when the burst error is corrected.

Fig. 5 är ett detaljerat blockschema av den utsignalväljande kretsen 6 i fig. 2 innehållande kriteriet för fastställande och bedömning av kommunikationsbanans tillstànd genom användande av de avkodade resultaten fràn den skurfelkorrigerande kretsen 5 och 512' 145 6 den slumpfelkorrigerande kretsen 7 i fig. 2. I fig. 5 betecknar hänvisningssiffran 32 en ingàngsterminal för data som korrigerats genom användande av utsignalen från den slumpfelkorrigerande kretsen 7, 33 en ingångsterminal för data som korrigerats genom användande av utsignalen från den skurfelkorrigerande kretsen 5, 34 en exklusiv ELLER-krets för jämförelse av data korrigerade av den slumpfelkorrigerande kretsen 7 och data korrigerade av den skurfelkorrigerande kretsen 5, 35 en ingàngsterminal för detekteringssignalen för okorrigerbara fel från terminalen 24 relaterad till den slumpfelkorrigerande kretsen 7, 36 en ingángsterminal för detekteringssignalen för okorrigerbara fel från terminalen 31 relaterad till den skurfelkorrigerandeIkretsen 5, 37 en utsignalväljande omkopplare för val av antingen data korrigerade av den slumpfelkorrigerande kretsen 7 eller data korrigerade av den skurfelkorrigerande kretsen 5, samt 38 en utsignalväljande styrkrets för generering av en okorrigerbar signal till terminalen 10 (visas i fig. 2 och 4) i beroende av detekteringssignalerna för okorrigerbara fel inmatade från den slumpfelkorrigerande kretsen 7 och den skurfelkorrigerande kretsen 5 till ingàngsterminalerna 35 och 36, och för generering av en styrsignal för styrning av den utsignalvälj ande omkopplaren 37 i enlighet med feldetekteringssignalerna och utsignalen fràn den exklusiva ELLER-kretsen 34 som jämför data inmatade till terminalen 32, som har korrigerats av den slumpfelkorrigerande kretsen 7, och data som inmatats till terminalen 33 som har korrigerats av den skurfelkorrigerande kretsen 5.Fig. 5 is a detailed block diagram of the output signal selecting circuit 6 of Fig. 2 containing the criterion for determining and judging the state of the communication path by using the decoded results from the burst error correcting circuit 5 and the random error correcting circuit 7 of Fig. 2. In Fig. 5, reference numeral 32 denotes an input terminal for data corrected by using the output signal from the random error correcting circuit 7, 33 an input terminal for data corrected by using the output signal from the burst error correcting circuit 5, 34 an exclusive OR circuit for comparing data corrected by the random error correcting circuit 7 and data corrected by the burst error correcting circuit 5, 35 an input terminal for the uncorrectable error detection signal from the terminal 24 related to the random error correcting circuit 7, 36 an input terminal for the uncorrectable error detection signal from the terminal 31 related to the burst error correcting circuit 5, 37 an output signal selecting switch for selecting either data corrected by the random error correcting circuit 7 or data corrected by the burst error correcting circuit 5, and 38 an output signal selection control circuit for generating an uncorrectable signal to the terminal 10 (shown in Figs. 2 and 4) in response to the uncorrectable error detection signals input from the random error correcting circuit 7 and the burst error correcting circuit 5 to the input terminals 35 and 36, and for generating a control signal for controlling the output signal selection switch 37 in accordance with the error detection signals and the output from the exclusive OR circuit 34 which compares data input to the terminal 32, which has been corrected by the random error correcting circuit 7, and data input to the terminal 33 which has been corrected by the burst error correcting circuit 5.

Fig. 6 är en tabell som visar kriteriet för styrning av den utsignalväljande kretsen 37 och som ingår i väljarkretsen 6 samt kriteriet för bestämning av den okorrigerbara felsignalen till terminalen 10.Fig. 6 is a table showing the criterion for controlling the output signal selecting circuit 37 included in the selector circuit 6 and the criterion for determining the uncorrectable error signal to the terminal 10.

Funktionen kommer nu att beskrivas. Ett meddelande som kodats på sändarsidan och inkluderar fel adderade utmed kommunikationsbanan mottages pà ingàngsterminalen. 1. Två n-bits syndrom, S1, S3 uttryckta genom vektorer i. polynombasen :i det finita fältet genereras av den syndromgenererande kretsen 2. De två n bitar \ 512 1245 '7 långa syndromen SU Sainmatas sedan till den slumpfelkorrigeran- de kretsen 7 och syndromomvandlingskretsen 4. I den slump- felkorrigerande kretsen 7 lagras de inmatade syndromen S1, S3 i registret 13 och utmatas dessa såsom adressen till nämnda data- ROM 8 via adresstyrkretsen 20 till adressutgàngsterminalen 21.The function will now be described. A message encoded on the transmitter side and including errors added along the communication path is received at the input terminal. 1. Two n-bit syndromes, S1, S3 expressed by vectors in the polynomial basis :in the finite field are generated by the syndrome generating circuit 2. The two n-bit \ 512 1245 '7 long syndromes SU are then input to the random error correcting circuit 7 and the syndrome conversion circuit 4. In the random error correcting circuit 7, the input syndromes S1, S3 are stored in the register 13 and are output as the address of the said data ROM 8 via the address control circuit 20 to the address output terminal 21.

Syndromen S1, S3 omvandlas av nämnda data-ROM 8 från vektorut- trycket i polynombasen i det finita fältet till det exponentiella uttrycket av det finita elementets primitiva element, log Sloch log S3. De omvandlade syndromen log S1 och log S, lagras i registret 16 med hjälp av dataingàngsterminalen 22 samt registret 17. På basis av de exponentiellt uttryckta syndromen log S, och log S3 som lagrats i registret 16 beräknas den konstanta termen (log S3 - 3 x log S 1) av det normaliserade felpositionspolynomet genom användande av adderingskretsen 14 och den komplementära sifferkretsen 15, och den konstanta termen (log S3 - 3 x log S1) utmatas sedan sàsom adress till nämnda data-ROM 8 via adresstyr- kretsen 2Ö och adressutgàngsterminalen 21. Den konstanta termen (log S3 - 3 x log S1) omvandlas sedan av nämnda data-ROM 8 till tvâ radikaler i = log a* och j = log ai av det normaliserade felpositionspolynomet. Här är a ett primitivt element av det finita fältet och a* samt a* radikaler av det normaliserade felpositionspolynomet, dvs. de representerar den normaliserade felpositionen. De tvà radikalerna i = log ai och j = log ai av felpositionspolynomet som normaliserats av nämnda data-ROM 8 leds genom dataingàngsterminalen 22 och registret 17 och adderas av adderingskretsen 14 till log S, samt lagras i räknarkretsen 18 för beräkning av den sanna felpositionen. Vid denna tidpunkt kontrolleras resultatet av additionen av registret 17, och om det är ett okorrigerbart tillstànd, utmatas en detekteringssignal indikerande okorrigerbart fel till terminalen 24. Den sanna felpositionen som lagrats i räknarkretsen 18 räknas ned, och när innehálletzi räknarkretsen 18 blir noll avges en felkorrigerings- puls genom ELLER-kretsen 19 till den exklusiva ELLER-kretsen ll- afi Å andra sidan omvandlas de tvâ n bitar långa syndromen S1 och S3 som inmatats som inmatats till syndromomvandlingskretsen 4 till 5'12' 1115 8 2n bitar lànga syndrom som därefter inmatas till den skurfelkor- rigerande kretsen 5. För exempelvis (511, 493) BCH-koder med följande genererande polynom: g(x) = x" + x" + x" +"x1° + x" + X7 + X6 + X3 + 1 utföres omvandlingen i enlighet med följande ekvationer: S10 = S17 + S14 + S13 + S11 + S10 + S + S * S33 + S3! 37 34 S11 = S18 + S15 + S14 + S12 + S11 + S10 * S38 + S35 * S34 * 531 * S30 S12-= S16 + S15-+ S13 + S12 + S11 + S10 _* S36:+ S35 + S33 + S31 + S30 S13 = S16 + S12 + S36 + S33 + S32 Sl¿ = §l7 + S13 + S37 + S34 + S33 sls = sig + s14 + S10 + S38 + S35 + S34 + S30 516 = 517 + 515 + S14 + S13 * S37 * S36 * S35 * S34 * S33 S17 = 518 + S17 + S16 + S15 + S13 + S11 + 538 + S36 * S35 + S33 + S31 s18 = sls + slö + sla + slz + sl, + slo + sas + S33 + saz + ss, + sso S19 = sl? + S14 + slg + slz + sl, + S37 + S34 + S33 + S32 + S3! 511° = S18 * S1? * 515 * S12 * S11 + S38 + S37 + S35 + S32 + Ssx + S + S12 + S + S s1,1 = s lo + S 36 33 32 3° S112 = 510 + S30 s1,3 = S11 * 531 512 145 S114 = S12 * S32 S115 = S17 + Sl¿ i-t-Sll + S10 + S + + S37 + S34 31 S146 = 518 + S15 + S12 + S11 + S38 + 535 * 532 + S31 S117 = 516 + S13 + 512 + S10 + S35 * S33 + S32 J' S30 I den skurfelkorrigerande kretsen 5 sluts omkopplaren 27 för styrning av àterkopplingen och vrids väljaromkopplarna 28 till sidorna "a" anslutna till ingàngsterminalerna 25, så att de två n bitar långa syndromen som omvandlats av syndromomvandlings- kretsen 14 inmatas till fördröjningskretsen 26 :i den linjära àterkopplingsskiftregisterkretseni med en längd pà 2n bitar.The syndromes S1, S3 are converted by said data ROM 8 from the vector expression in the polynomial basis in the finite field to the exponential expression of the primitive element of the finite element, log S and log S3. The converted syndromes log S1 and log S2 are stored in the register 16 by means of the data input terminal 22 and the register 17. On the basis of the exponentially expressed syndromes log S1 and log S3 stored in the register 16, the constant term (log S3 - 3 x log S1) of the normalized error position polynomial is calculated by using the adder circuit 14 and the complementary digit circuit 15, and the constant term (log S3 - 3 x log S1) is then output as an address to said data ROM 8 via the address control circuit 20 and the address output terminal 21. The constant term (log S3 - 3 x log S1) is then converted by said data ROM 8 into two radicals i = log a* and j = log ai of the normalized error position polynomial. Here a is a primitive element of the finite field and a* and a* are radicals of the normalized error position polynomial, i.e. they represent the normalized error position. The two radicals i = log ai and j = log ai of the error position polynomial normalized by the data ROM 8 are passed through the data input terminal 22 and the register 17 and are added by the adding circuit 14 to log S, and stored in the counter circuit 18 for calculating the true error position. At this time, the result of the addition is checked by the register 17, and if it is an uncorrectable condition, a detection signal indicating uncorrectable error is output to the terminal 24. The true error position stored in the counter circuit 18 is counted down, and when the content of the counter circuit 18 becomes zero, an error correction pulse is output through the OR circuit 19 to the exclusive OR circuit 11- afi On the other hand, the two n-bit syndromes S1 and S3 inputted to the syndrome conversion circuit 4 are converted into 5'12' 1115 8 2n-bit syndromes which are then inputted to the burst error correction circuit 5. For example, for (511, 493) BCH codes with the following generating polynomials: g(x) = x" + x" + x" +"x1° + x" + X7 + X6 + X3 + 1 the conversion is carried out in accordance with the following equations: S10 = S17 + S14 + S13 + S11 + S10 + S + S * S33 + S3! 37 34 S11 = S18 + S15 + S14 + S12 + S11 + S10 * S38 + S35 * S34 * 531 * S30 S12-= S16 + S15-+ S13 + S12 + S11 + S10 _* S36:+ S35 + S33 + S31 + S30 S13 = S16 + S12 + S36 + S33 + S32 Sl¿ = §l7 + S13 + S37 + S34 + S33 sls = sig + s14 + S10 + S38 + S35 + S34 + S30 516 = 517 + 515 + S14 + S13 * S37 * S36 * S35 * S34 * S33 S17 = 518 + S17 + S16 + S15 + S13 + S11 + 538 + S36 * S35 + S33 + S31 s18 = sls + slö + sla + slz + sl, + slo + sas + S33 + saz + ss, + sso S19 = sl? + S14 + slg + slz + sl, + S37 + S34 + S33 + S32 + S3! 511° = S18 * S1? * 515 * S12 * S11 + S38 + S37 + S35 + S32 + Ssx + S + S12 + S + S s1,1 = s lo + S 36 33 32 3° S112 = 510 + S30 s1,3 = S11 * 531 512 145 S114 = S12 * S32 S115 = S17 + Sl¿ i-t-Sll + S10 + S + + S37 + S34 31 S146 = 518 + S15 + S12 + S11 + S38 + 535 * 532 + S31 S117 = 516 + S13 + 512 + S10 + S35 * S33 + S32 J' S30 In the burst error correcting circuit 5, the feedback control switch 27 is closed and the selector switches 28 are turned to the sides "a" connected to the input terminals 25, so that the two n-bit syndromes converted by the syndrome conversion circuit 14 are input to the delay circuit 26 in the linear feedback shift register circuit with a length of 2n bits.

Väljaromkopplaren 28 vrids sedan till de linjära áterkopplings- skiftregisterkretssidorna "b" och skurfelmönstret kontrolleras av làskretsen 29 (nolldetektering) under skiftningsoperationens utförande. Om skurfelmönstret detekteras av làskretsen 29 (nolldetektering) öppnas omkopplaren 27 och utmatas felmönstret seriellt fràn felmönsterutgángsterminalen 31 till den exklusiva ELLER-kretsen ll-b. Om vid denna tidpunkt inget felmönster detekteras av skiftningsoperationen över kodens längd utmatas signalen avseende ett okorrigerbart fel detekterat av láskretsen l29 (nolldetektering) till terminalen 30.The selector switch 28 is then turned to the linear feedback shift register circuit sides "b" and the burst error pattern is checked by the latch circuit 29 (zero detection) during the execution of the shift operation. If the burst error pattern is detected by the latch circuit 29 (zero detection), the switch 27 is opened and the error pattern is serially output from the error pattern output terminal 31 to the exclusive OR circuit 11-b. If at this time no error pattern is detected by the shift operation over the length of the code, the signal regarding an uncorrectable error detected by the latch circuit 129 (zero detection) is output to the terminal 30.

Om ett felmönster detekteras i den slumpfelkorrigerande kretsen 7 eller den skurfelkorrigerande kretsen 5 läses det mottagna meddelandet ut från fördröjningskretsen 3, i vilken det mottagna meddelandet lagrats, varvid respektive felmönster sonldetekterats i den slumpfelkorrigerande kretsen 7 och den skurfelkorrigerande kretsen 5 separat kombineras med det mottagna meddelandet genom de exklusiva ELLER-kretsarna 11-a, ll-b, så att slump- och skurfelen.korrigeras för tillhandahållande av respektive avkodade meddelanden. Därefter inmatas de avkodade meddelanden som korrigerats av den slumpfelkorrigerande kretsen 7 och den 512 145 10 skurfelkorrigerande kretsen 5 samt utsignalerna fràn detekte- ringsterminalerna 24, 30 för okorrigerbara fel, som är anslutna till den slumpfelkorrigerande kretsen 7 och den skurfelkorrige- rande kretsen 5, till den utsignalväljande kretsen 6. I den utsignalväljande kretsen 6 jämförs respektive meddelanden som inmatats från den slumpfelkorrigerande kretsen.7 och den skurfel- korrigerande kretsen 5 genom den exklusiva ELLER-kretsen 34.If an error pattern is detected in the random error correcting circuit 7 or the burst error correcting circuit 5, the received message is read out from the delay circuit 3 in which the received message is stored, the respective error patterns detected in the random error correcting circuit 7 and the burst error correcting circuit 5 are separately combined with the received message through the exclusive OR circuits 11-a, 11-b, so that the random and burst errors are corrected to provide the respective decoded messages. Then, the decoded messages corrected by the random error correcting circuit 7 and the burst error correcting circuit 5 and the output signals from the uncorrectable error detection terminals 24, 30, which are connected to the random error correcting circuit 7 and the burst error correcting circuit 5, are input to the output signal selecting circuit 6. In the output signal selecting circuit 6, the respective messages input from the random error correcting circuit 7 and the burst error correcting circuit 5 are compared through the exclusive OR circuit 34.

Resultatet av jämförelsen genom den exklusiva ELLER-kretsen 34 samt detekteringssignalerna avseende okorrigerbara fel från terminalerna 24, 30 inmatas till utsignalväljarstyrkretsen 36, vilken i sin tur styr den utsignalväljande omkopplaren 37 i enlighet med kriteriet för utsignalval som visas i fig. 6. Om sålunda båda detekteringssignalerna avseende okorrigerbart fel från terminalerna 24, 30 visar korrektion och utsignalen fràn den exklusiva ELLER-grinden 34, som jämför respektive avkodade meddelanden, visar att de avkodade meddelandena är identiska, så vrids den utsignalväljande omkopplaren 37 till sin "a"-sida för att välja utsignalen från den slumpfelkorrigerande kretsen 7 via den exklusiva ELLER-kretsen ll-a, om detekteringssignalen avseende okorrigerbart fel frán signalen 24 visar korrektion och detekteringssignalen avseende okorrigerbart fel frán terminalen 30 visar detektering av ett okorrigerbart fel, så vrids den utsignalväljande omkopplaren 37 till sin "a"-sida för att välja samma utsignal som ovan, om detekteringssignalen avseende okorrigerbart fel från terminalen 30 visar korrektion och detekteringssignalen avseende okorrigerbart fel fràn terminalen 24 visar detektering av ett okorrigerbart fel, så vrids den utsignalväljande omkopplaren 37 till sin "b"-sida för att välja utsignalen från den skurfelkorrigerande kretsen 5 via den exklusiva ELLER-kretsen ll-b, och i andra fall utmatas den signal som representerar förekomsten av okorrigerbart fel till termina- len 10. Det slutliga avkodade meddelandet som valts av den utsignalväljande kretsen 6 utmatas via utgàngsterminalen 9.The result of the comparison by the exclusive OR circuit 34 and the uncorrectable error detection signals from the terminals 24, 30 are input to the output selection control circuit 36, which in turn controls the output selection switch 37 in accordance with the output selection criterion shown in Fig. 6. Thus, if both the uncorrectable error detection signals from terminals 24, 30 indicate correction and the output from exclusive OR gate 34, which compares the respective decoded messages, indicates that the decoded messages are identical, then the output selection switch 37 is turned to its "a" side to select the output from random error correcting circuit 7 via exclusive OR circuit 11-a, if the uncorrectable error detection signal from signal 24 indicates correction and the uncorrectable error detection signal from terminal 30 indicates detection of an uncorrectable error, then the output selection switch 37 is turned to its "a" side to select the same output as above, if the uncorrectable error detection signal from terminal 30 indicates correction and the uncorrectable error detection signal from terminal 24 indicates detection of an uncorrectable error. error, the output signal selecting switch 37 is turned to its "b" side to select the output signal from the burst error correcting circuit 5 via the exclusive OR circuit 11-b, and in other cases, the signal representing the occurrence of uncorrectable error is output to the terminal 10. The final decoded message selected by the output signal selecting circuit 6 is output via the output terminal 9.

I den ovan beskrivna utföringsformen är den slumpfelkorrigerande kretsen 7 anordnad med en krets för utförande av operationer modulo 2"-1, men den anordnade slumpfelkorrigerande kretsen kan 512 145 ll använda en konventionell skiftregisterkrets med linjär period.In the above-described embodiment, the random error correcting circuit 7 is provided with a circuit for performing operations modulo 2"-1, but the provided random error correcting circuit may use a conventional shift register circuit with linear period.

Vidare är kodlängden ej slutgiltigt begränsad, utan en liknande effekt kan även framkallas med en kortare kod.Furthermore, the code length is not definitively limited, but a similar effect can also be produced with a shorter code.

Såsom beskrivits ovan kan, i enlighet med föreliggande upp- finning, en krets med högre tillförlitlighet för avkodning av en BCH-kod åstadkommas för korrigering av ett komplext eller sammansatt fel genom tillhandahållande av en utsignalväljande krets innehållande kriteriet för val av utsignal från den slumpfelkorrigerande kretsen respektive den skurfelkorrigerande kretsen.As described above, according to the present invention, a circuit with higher reliability for decoding a BCH code can be provided for correcting a complex or compound error by providing an output signal selecting circuit containing the criterion for selecting the output signal from the random error correcting circuit and the burst error correcting circuit, respectively.

Fackmannen inser vidare att ovanstående beskrivning avser en föredragen utföringsform av den beskrivna anordningen och att olika förändringar och modifieringar kan företagas inom upp- finningens ram.Those skilled in the art will further recognize that the above description relates to a preferred embodiment of the described device and that various changes and modifications may be made within the scope of the invention.

Claims (1)

1. 512 145 12, PATENTKRAV Krets för samtidig detektering och korrigering av ett kombinerat komplext fel i ett digitalt kommunikationssystem, innefattande - en första enhet (2, 7, 11-a) för korrigering av slumpfel i kodsignalen, - en andra enhet (4, 5, 11-b) för korrigering av skurfel, och - en tredje enhet (6) ansluten till den första och den andra enheten kännetecknad av att den mottagna signalen är kodad med en Bach-kod som använder ett genererande poiynem got) = x” + x” + x” + x'° + x* + X7 + X6 + X3 + xl, att ett första och ett andra n-bitars syndrom (S1, S3) på i och för sig känt sätt genereras i den första enheten (2, 11-a), ' att den andra enheten (4, 5, 11-b) innehåller en syndromkonverteringskrets (4) för beräkning av ett Zn-bitars syndrom (S) ur de två n-bitars syndromen som genererats i den första enheten, och att den tredje enheten (6) väljer utsignalen från den första eller andra enheten som gensvar på avkodningstillstånden för den första och andra enheten, varvid en omkopplare för selektiv utmatning väljer utsignalen från den enhet som indikerar ett korrigerbart fel och avger en signal avseende detektering av ett icke korrigerbart fel om båda korrigeringsenheterna (för slumpfel eller skurfel) indikerar ett icke korrigerbart fel eller om båda korrigeringsenheterna indikerar korrigerbara fel men korrektionsmönstren som avges av de båda korrigeringsenheterna ej är identiska. Krets enligt krav 1, kännetecknad av organ (8) för uppslagning i en tabell som lagrar i förväg beräknade radikal-data för felpositionspolynom och för erhållande av en normaliserad felposition.A patent for simultaneous detection and correction of a combined complex error in a digital communication system, comprising - a first unit (2, 7, 11-a) for correcting random errors in the code signal, - a second unit (4 , 5, 11-b) for correcting burst errors, and - a third unit (6) connected to the first and the second unit, characterized in that the received signal is coded with a Bach code using a generating poiynem got) = x "+ X" + x "+ x '° + x * + X7 + X6 + X3 + xl, that a first and a second n-bit syndrome (S1, S3) are generated in a manner known per se in the first unit (2, 11-a), that the second unit (4, 5, 11-b) contains a syndrome conversion circuit (4) for calculating a Zn-bit syndrome (S) from the two n-bit syndromes generated in the first unit, and that the third unit (6) selects the output signal from the first or second unit in response to the decoding states of the first and second units, wherein a switch selector output selector selects the output signal from the unit indicating a correctable error and emits a signal for detecting a non-correctable error if both correction units (for random error or burst error) indicate a non-correctable error or if both correction units indicate correctable errors but the correction patterns given of the two correction units are not identical. Circuit according to Claim 1, characterized by means (8) for look-up in a table which stores pre-calculated radical data for fault position polynomials and for obtaining a normalized fault position.
SE8904169A 1989-05-15 1989-12-11 Device for correction of burst and random errors SE512145C2 (en)

Applications Claiming Priority (1)

Application Number Priority Date Filing Date Title
JP1121909A JPH02301226A (en) 1989-05-15 1989-05-15 Composite error correction bch decoding circuit

Publications (3)

Publication Number Publication Date
SE8904169D0 SE8904169D0 (en) 1989-12-11
SE8904169L SE8904169L (en) 1990-11-16
SE512145C2 true SE512145C2 (en) 2000-01-31

Family

ID=14822911

Family Applications (1)

Application Number Title Priority Date Filing Date
SE8904169A SE512145C2 (en) 1989-05-15 1989-12-11 Device for correction of burst and random errors

Country Status (11)

Country Link
JP (1) JPH02301226A (en)
KR (1) KR940002112B1 (en)
CA (1) CA2011103C (en)
CH (1) CH680031A5 (en)
DE (1) DE4005533C2 (en)
FR (1) FR2646976B1 (en)
GB (1) GB2232043B (en)
IT (1) IT1237726B (en)
NL (1) NL191348C (en)
NO (1) NO305879B1 (en)
SE (1) SE512145C2 (en)

Families Citing this family (4)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
JPH03235528A (en) * 1990-02-13 1991-10-21 Sharp Corp Bch code decoding circuit
NL9101376A (en) * 1990-08-16 1992-03-16 Digital Equipment Corp AN IMPROVED ERROR DETECTION CODING SYSTEM.
US5377208A (en) * 1991-11-02 1994-12-27 U.S. Philips Corporation Transmission system with random error and burst error correction for a cyclically coded digital signal
JP2944489B2 (en) * 1995-10-14 1999-09-06 日本電気株式会社 Error correction method in wireless transmission system

Family Cites Families (10)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
US3544963A (en) * 1968-12-27 1970-12-01 Bell Telephone Labor Inc Random and burst error-correcting arrangement
JPS5975732A (en) * 1982-10-22 1984-04-28 Mitsubishi Electric Corp Decoder
US4592054A (en) * 1982-10-22 1986-05-27 Mitsubishi Denki Kabushiki Kaisha Decoder with code error correcting function
GB2131253A (en) * 1982-11-24 1984-06-13 Motorola Ltd Error-correcting decoder
GB2136248A (en) * 1983-02-25 1984-09-12 Philips Electronic Associated Text error correction in digital data transmission systems
US4646303A (en) * 1983-10-05 1987-02-24 Nippon Gakki Seizo Kabushiki Kaisha Data error detection and correction circuit
JPS61105931A (en) * 1984-10-30 1986-05-24 Mitsubishi Electric Corp decoding device
JPS6276825A (en) * 1985-09-30 1987-04-08 Hitachi Ltd Code error correcting method
JPS62268215A (en) * 1986-05-16 1987-11-20 Fuji Electric Co Ltd Galois field arithmetic circuit
JPS6427322A (en) * 1988-04-21 1989-01-30 Sony Corp Arithmetic circuit for galois field

Also Published As

Publication number Publication date
NL191348B (en) 1995-01-02
IT8968156A0 (en) 1989-12-22
DE4005533A1 (en) 1990-12-13
IT8968156A1 (en) 1991-06-22
IT1237726B (en) 1993-06-15
JPH02301226A (en) 1990-12-13
CA2011103A1 (en) 1990-11-15
NO894757D0 (en) 1989-11-29
NO894757L (en) 1990-11-16
KR940002112B1 (en) 1994-03-17
NL191348C (en) 1995-06-01
NO305879B1 (en) 1999-08-09
GB9000712D0 (en) 1990-03-14
DE4005533C2 (en) 1998-01-22
FR2646976B1 (en) 1996-08-02
NL8903084A (en) 1990-12-03
SE8904169D0 (en) 1989-12-11
KR900019400A (en) 1990-12-24
GB2232043A (en) 1990-11-28
SE8904169L (en) 1990-11-16
CA2011103C (en) 1996-01-02
CH680031A5 (en) 1992-05-29
GB2232043B (en) 1993-07-14
FR2646976A1 (en) 1990-11-16

Similar Documents

Publication Publication Date Title
US5179560A (en) Apparatus for decoding bch code for correcting complex error
KR102808297B1 (en) Multi-mode channel coding with mode specific coloration sequences
US4916702A (en) Elongated burst trapping
KR100659265B1 (en) C.R.C. with parity bits added in reverse order Error detection device and method of code
EP0061345A2 (en) Processing circuits for operating on digital data words which are elements of a Galois field
US4897839A (en) Coding and decoding method
WO1998018209A1 (en) Device and method for viterbi decoding
SE512145C2 (en) Device for correction of burst and random errors
JPH0221180B2 (en)
US3164804A (en) Simplified two-stage error-control decoder
US5416786A (en) Error correction circuit for BCH codewords
RU2035123C1 (en) Device for decoding linear codes
US20030041300A1 (en) Universal device for processing Reed-Solomon forward error-correction encoded messages
JPH05284044A (en) Transmitter for performing random error and burst error correction, receiver, decoder and video phone
EP0455992B1 (en) Electronic device for parallel correction of data streams protected with error detection by cyclic redundancy check
KR0183279B1 (en) Decoder Using the Modified Euclidean Algorithm
KR900001066Y1 (en) Clear signal counting circuit of error correcting decoder circuit
KR0155762B1 (en) Reed-Solomon Decoder with Efficient Error Correction
KR100407131B1 (en) Reed solomon decoder using combinational circuits
JPH07264078A (en) BCH coding apparatus and BCH coding method
KR960003051B1 (en) Error location generating circuit
KR19980041383A (en) Parallel Traversal Redundancy Code Encoder and Decoder
EP1337044A2 (en) Code generator circuit
JPH06181442A (en) Error correction circuit
JPH0619730A (en) Automatic switch check system for parity

Legal Events

Date Code Title Description
NUG Patent has lapsed