Arrangements and method relating to transmission of digital data

(54) NAME Devices and procedure related to incorrectly corrected transmission of digital data (56) PUBLICATIONS Cited: - - - (57) SUMMARY:

The present invention relates to a receiving device which receives digital decoded data signals transmitted over a channel. The data signal comprises sequences which are divided into blocks and the receiving device includes error correction means which provide a number of alternative blocks. In addition, it includes error detecting means and storage means for storing information related to each possible block position in a sequence. The error detecting means includes a differential CRC decoder which includes first decoding means (20A) to decode a sequence of blocks using a reference sequence to give a reference syndrome, and a second decoding means (20B) to decode selected alternative differential blocks of the sequence which is obtainable through the error correction means. The differential blocks are calculated as a difference between corresponding blocks in the reference sequence and alternative blocks to give differential syndrome. The resulting syndromes are calculated as a sum of the reference syndrome and of a number of differential syndromes. The invention also relates to a system which includes such a receiving device, and error-correcting CRC decoders and a method for detecting errors in a CRC-encoded digital signal.

<img file="SE519003C2_D0001.tif" />

The numbers in brackets indicate international identification code, INID code. Letters in clamps indicate international document code.

PRV Patent uses the following document codes for its patents code clear text code clear text

A general ti In Available patert lens search

B paving script *

BJ corrected exposition *

C patent *

Cl patenLScript *

C2 patenLScript

CJ corrected patents

CJ lawLtd patent letter ·

C8 corrected front page to! patent

E patent in amended version

E8 corrected front page to patent in amended version E9 corrected patent text in amended version

L widely available

For translation of the requirements of European patent application

T2 correction of translation of the requirements of the European palette application

T3 translation of European patent

T4 translation of European patent in amended form

TJ corrected translation of European patent

T8 corrected translation of European patent

T9 corrected translation of European Patents * published under older legislation / National Codes

<td>.AP</td><td>African Regional</td><td>CN</td><td>China</td>

<td></td><td>Industrial Property</td><td>CO</td><td>Colombia</td>

<td></td><td>Organization (ARIPO)</td><td>CR</td><td>Costa Rica</td>

<td>EA</td><td>Euroasian Patent Office</td><td>CU</td><td>Cuba</td>

<td></td><td>(E.APO)</td><td>CV</td><td>Cape Verde</td>

<td>EP</td><td>European Patent Office</td><td>CY</td><td>Cyprus</td>

<td></td><td>(EPO)</td><td>CZ</td><td>The Czech Republic</td>

<td>OA</td><td>African Intellectual</td><td>THE</td><td>Germany</td>

<td></td><td>Property Organization</td><td>DJ</td><td>djibouti</td>

<td></td><td>(O.API)</td><td>DK</td><td>Denmark</td>

<td>WO</td><td>World Intellectual</td><td>DM</td><td>dominica</td>

<td></td><td>Property Organization</td><td>DO</td><td>Dominican Republic</td>

<td></td><td>(WIPO)</td><td>DZ</td><td>Algeria</td>

<td>IB</td><td>WIPO (in some cases)</td><td>EC</td><td>Ecuador</td>

<td></td><td></td><td>EE</td><td>Estonia</td>

<td>A.D</td><td>Andorra</td><td>EC</td><td>Egypt</td>

<td>AE</td><td>United Arab Emirates</td><td>ES</td><td>Spain</td>

<td>AF</td><td>Afghanistan</td><td>ET</td><td>Ethiopia</td>

<td>AG</td><td>Antigua</td><td>Fl</td><td>Finland</td>

<td>AI</td><td>anguilla</td><td>FJ</td><td>Fiji islets</td>

<td>AL</td><td>Albania</td><td>FK</td><td>Falconry the same</td>

<td>AM</td><td>Armenia</td><td>FR</td><td>France</td>

<td>AN</td><td>Netherlands Antilles</td><td>GA</td><td>Gabon</td>

<td>AO</td><td>angola</td><td>GB</td><td>UK</td>

<td>ARE</td><td>Argentina</td><td>DG</td><td>grenada</td>

<td>AT</td><td>Austria</td><td>GIVE</td><td>Georgia</td>

<td>AU</td><td>Australia</td><td>GH</td><td>Ghana</td>

<td>AZ</td><td>Azerbaijan</td><td>GI</td><td>Gibraltar</td>

<td>BA</td><td>Bosnia too</td><td>GM</td><td>gambia</td>

<td></td><td>Herzegovina</td><td>GN</td><td>guinea</td>

<td>BB</td><td>barbados</td><td>GQ</td><td>Equatorial Guinea</td>

<td>BD</td><td>bangladesh</td><td>GR</td><td>Greece</td>

<td>ASK</td><td>Belgium</td><td>GT</td><td>Guatemala</td>

<td>BF</td><td>Burkina Faso</td><td>GW</td><td>Guinea Bissau</td>

<td>BG</td><td>Bulgaria</td><td>GY</td><td>guyana</td>

<td>BH</td><td>bahrain</td><td>HK</td><td>Hong Kong</td>

<td>Bl</td><td>Burundi</td><td>HN</td><td>honduras</td>

<td>BJ</td><td>benin</td><td>HR</td><td>Croatia</td>

<td>BM</td><td>bermuda</td><td>HT</td><td>Haiti</td>

<td>STAY</td><td>bolivia</td><td>HU</td><td>Hungary</td>

<td>BR</td><td>Brazil</td><td>ID</td><td>Indonesia</td>

<td>BS</td><td>Bahamaöama</td><td>IU</td><td>Ireland</td>

<td>BT</td><td>Bhutan</td><td>IL</td><td>israel</td>

<td colspan="2">BW Botswana</td><td>IN</td><td>India</td>

<td>VILLAGE</td><td>Belarus</td><td>IQ</td><td>Iraq</td>

<td>BZ</td><td>belize</td><td>IR</td><td>Iran</td>

<td>CA</td><td>Canada</td><td>ICE</td><td>Iceland</td>

<td>CF</td><td>central African</td><td>ΓΤ</td><td>Italy</td>

<td></td><td>Republic</td><td>JM</td><td>jamaica</td>

<td>CG</td><td>Congo</td><td>YES</td><td>Jordan</td>

<td colspan="2">CH Switzerland</td><td>JP</td><td>Japanese</td>

<td>Cl</td><td>iVORY COAST</td><td>KE</td><td>Kenya</td>

<td>CL</td><td>chile</td><td colspan="2">KG Kyrgyzstan</td>

<td colspan="2">CM Cameroon</td><td colspan="2">KH Cambodia</td>

KI Kiribati KM Comorema KN St Kitts KP Dem. People's Republic of Korea KR Republic of Korea KW Kuwait

KY Cayman Island KZ Kazakhstan LA Laos LB Lebanon LC Saint Lucia Ll Liechtenstein LK Sri Lanka LR Liberia LS Lesotho LT Lithuania LU Luxembourg LV Latvia LY Libya MA Morocco MC Monaco MD Moldova MG Madagascar MK Macedonia ML Mali MM Mayanmar MN Mongolia MR Mauritania MS Monsterrat MT Malta MU Mauritius MV Maldivema MW Malawi MX Mexico MY Malaysia MZ Mozambique NA Namibia NG Nigeria NI Nicaragua NL Netherlands NO Norway NP Nepal NR Nauru NZ New Zealand OM Oman PA Panama PE Peru PG Papua New Guinea PH Philippines PK Pakistan PL Poland PT Portugal PY Paraguay RO Romania

RU Russian Federation RW Rwanda

SA Saudi Arabia SB Solomon Islands SC Seychelles SD Sudan

SE Sweden SG Singapore SH St Helena SI Slovenia SK Slovakia SL Sierra Leone SM San Marino SN Senegal SO Somalia SR Suriname ST Sao Thomé SV El Salvador SY Syria SZ Swaziland TD Chad TG Togo TH Thailand TJ Tajikistan TM Turkmenistan TN Tunisia TO Tonga TR Turkey TT Trinidad and Tobago TV Tuvalu TW Taiwan TZ Tanzania UA Ukraine UG Uganda

US United States (USA) UY Uruguay LIZ Uzbekistan

VA Vatican City VC St Vincent VE Venezuela VG Virgin Islands UN VietNam VU Vanuatu WS Samoa YD South Yemen YE Yemen YU Yugoslavia ZA South Africa ZM Zambia ZR Zaire ZW Zimbabwe

519 003

TECHNICAL FIELD

The present invention relates to devices, a system and a method in digital data transmission. When transmitting information, e.g. data communication and wireless communication, errors are generally always produced when signals are transmitted over a channel from the transmitting side to the receiving side. Coding is often used as a protection against distortion when data is transported over a channel. In particular, the present invention relates to a receiving device for receiving a digitally encoded data signal transmitted over a channel. The invention also relates to a system for transmitting digitally encoded data signals over channels. In addition, the invention relates to a fault detection device, in particular a so-called CRC (Cyclic Redundancy Check) decoder for detecting errors in a received CRC-encoded data signal. The invention also relates to a method for detecting errors in a CRC-encoded digital data signal.

BACKGROUND OF THE ART

A special case when coding is used as a protection against distortion is in mobile communication where a signal is transmitted via radio between a base station and a mobile phone. The longer the distance, the more the radio signal is attenuated and it is also subject to distortion in the form of fading produced by interference, so-called multiple fading, which means that a

519 003 signal can take many different paths from one point to another by reflecting on, for example, buildings, etc.

In some digital mobile communication standards, coding has been introduced in two steps to provide acceptable protection against loss of information. On the transmitting side, an error-detecting CRC encoder is introduced and, as a second step, an error-correcting block coding device is introduced. A signal is assumed to consist of a number of sequences where each sequence is divided into a number of blocks, each of said blocks in turn consisting of a number of bits. The error correction device works blockwise.

On the receiving side, an error-correcting decoder which decodes blocks into the overall sequence forms in a first step. In a second step, an error detecting CRC decoder is implemented to determine if the error correction decoder has made any incorrect decisions. The error detecting decoder acts on the entire sequence, which, as referred to above, consists of a number of blocks. When the error detecting CRC decoder detects that the decoded sequence is incorrect, it requests that the sequence be retransmitted. However, this can be very time-consuming as multiple attempts may be necessary. In addition, signaling between the sending and receiving side is required to administer the retransmissions and this requires capacity that could otherwise have been used for useful transmission of information. Therefore, what is needed is a way of finding the correct sequence as quickly as possible and thus avoiding, or at least reducing, retransmission. One known way of dealing with this problem is to have the error correction block decoder provide a number of alternative suggestions tested by the error detecting decoder. The probability that one of the proposals is correct will then be greater. However, it is difficult to select candidates. The error correction decoder is only capable of testing one

519 003 limited number of alternative solutions. Furthermore, if too many alternatives are to be tested, the risk of an incorrect proposal is increased. Alternatives can be selected if each data bit has an attribute in the form of so-called soft information which is a measure of the probability that the selected character (zero or one) is correct. Candidates are selected by inverting the bits with the lowest soft information, ie. the pieces which are most likely to be incorrect, are questioned first. One method that uses soft information is Chase's second algorithm. This is discussed in A class of algorithms information, 182, January concatenated degree project

University of

Flodin, for decoding block codes with channel measurement IEEE Trans. Inform. Theory, vol. IT-18, pages 1701972, by D. Chase.

code using soft at the Department of Technology, Gothenburg, December 1995, has the method

In Improved decoding of a decoding techniques, an Information Theory, Chalmers Sweden, by M. Fahami and P. was further evaluated. Both of these documents are incorporated herein by reference. The soft information method consists in calculating a number, for example M, of each block in the sequence. A number of blocks, N, is selected from the total number of blocks. The N blocks should be the worst blocks as far as this can be determined, ie. the blocks related to which the uncertainty is greatest. The total sequence is thereby produced and it consists of the permutations of the alternatives. So, in total, M needs^N alternative sequences are tested. However, it should be noted that there are a number of blocks that have never changed (the total sum minus N).

The error detecting CRC decoder is applied in such a way that the decoded total block sequence is multiplied by the parity check matrix (H) of the CRC polynomial. This can be realized such that the sequence is shifted through a shift register, which can be implemented, for example, as hardware or as software. When the entire sequence has been shifted through the shift register, the contents are read into

519 003 shift register out. This forms the syndrome for the decoding operation. If the syndrome contains only zeros, the sequence is accepted, otherwise it is rejected. The CRC coding can be defined by shifting the original sequence through a shift register in which the cells have a starting position different from zero. In this way, the shifting operation is made non-linear.

However, this can be seen as starting from an initial state in which there are zeros in all cells, that a block start is shifted which generates the defined start state and then the sequence to be encoded is shifted. On the decoding side, this corresponds to the beginning of the block being shifted first followed by the sequence to be decoded. If a block start is required, the parity check matrix is ​​increased by as many rows as the block start includes. However, the number of operations becomes large, and in addition, many shifts are required and such operations are generally long and demanding operations which in turn reduce performance or require a lot of power. One consequence of this may be, for example, that fewer alternatives than would actually be needed to be tested.

DISCLOSURE OF THE INVENTION

What is needed, therefore, is a receiving device, for receiving a digitally encoded data signal transmitted over a channel, which includes means of error correction and detection, which requires only a limited number of advanced and demanding computational operations to find a properly transmitted sequence, and which in particular, require fewer operations than hitherto known devices. In particular, a device is needed by which it is possible to save power and to lower production costs. A device is also needed through which a high performance can be provided and through which a correctly transmitted signal is efficient

519 003 can be found without requiring a large number of demanding operations, high power, etc.

A system for transmitting digitally encoded data signals over channels from a transmitting page to a receiving page is also needed.

<td>through which</td><td>above</td><td>said goal</td><td>achieved,</td><td>i.e.</td><td>where a correct</td><td>transmit</td>

<td>sequence easily</td><td>and</td><td>can quickly</td><td>be found</td><td>and</td><td colspan="2">which requires so few</td>

<td>retransmissions</td><td colspan="2">as possible.</td><td></td><td></td><td></td><td></td>

<td colspan="2">An error detection</td><td colspan="2">CRC decoder for</td><td>to</td><td>detect errors</td><td>in a</td>

<td>received CRC ·</td><td>coded</td><td colspan="2">digital data signal</td><td>as</td><td>has been decoded in</td><td>wrong-</td>

corrective means are also needed by which the above objectives can be achieved.

In addition, a method is also needed to detect errors in a CRC-encoded digital data signal sequence through which detection can be performed quickly and efficiently and reliably and requiring as few long and complicated computational operations as possible, and through which performance can be maintained at a high level. level. In addition, a process is needed by which the above goals are achieved and which is also cost-effective.

Therefore, a receiving device is referred to as referred to above, which includes error detecting means and storage means for storing information related to the possible, different, block alternatives, the error detecting means comprising a differential CRC decoder. Said differential decoders include first decoding means for decoding a sequence of blocks using a reference frequency to produce a reference syndrome. The second decoding means is used to decode selected, alternative, differential blocks of the sequence, where said alternatives can be obtained via the error correction means. The differential blocks are calculated as the difference between

519 003 corresponding blocks in the reference sequence and each alternative block, respectively, to provide differential syndrome. Thereafter, the sum of the reference syndrome and the respective differential syndrome is taken to give the resulting syndrome. The respective resulting syndromes are used to determine whether an alternative is correctly received or not.

In particular, the reference syndrome is calculated by multiplying the reference sequence by a parity control matrix for the CRC polynomial and the differential blocks are calculated as the difference (modulo 2) of the reference sequence blocks and the selected block options, respectively. In a particular implementation, the differential syndromes are generated by multiplying the differential blocks by the corresponding portion of the CRC polynomial parity control matrix.

In a special, advantageous implementation, the first decoding means comprise a first shift register and the reference syndrome is calculated by shifting the reference sequence once through said first shift register. In particular, the second decoding means comprise a second shift register with parameters that can be loaded with values ​​tabulated in the storage means for different positions according to the different alternatives and the differential blocks are shifted through said second shift register to give differential syndromes. In particular, for a sequence comprising K blocks, of which N blocks are selected to have M alternatives, the number of computational operations K becomes shifts to give the reference syndrome,

Nx (M1) shifts to calculate the differential syndromes and M^N additions (modulo 2) to calculate the resulting syndromes. The first and second decoding means may be implemented as hardware or software according to various embodiments. In particular, the second shift register is used in different ways for each block position which is one

519 003 results of the above statements and which allows for forward feed as well as back feed data, where the coefficients of CRC polynomials are used for back feed and individual vectors in the CRC polynomial H matrix are used for feed forward. In particular, given rows are stored in the H matrix in the storage means, for example a table, and the rows are given by how the original sequence is divided into blocks.

Therefore, there is also provided a system as referred to above which includes a number of transmitting devices and a number of receiving devices, the transmitting devices comprising error detecting CRC coding means and error correction block coding means through which a signal is transmitted to a receiving device which includes error correction means which find your number. block options in a sequence where said alternatives are provided to error-detecting CRC decoding means. The error detecting CRC decoders consist of a differential CRC decoder which includes first and second decoders. In addition, storage means are provided. The first decoding means are used to decode a sequence of blocks using a reference sequence to give a reference syndrome, while the second decoding means are used to decode alternative differential blocks of the original sequence given to the receiving means. The alternatives are provided by the error detecting means and information about the various alternatives is contained in the storage means. The differential blocks are calculated using the second decoding means as the difference between corresponding blocks in the reference sequence and each respective alternative block and the respective differential syndromes is obtained by multiplying the appropriate portions of the CRC polynomial parity control matrix. The resulting syndrome is calculated as the sum (modulo 2) of the reference syndrome and the respective differential syndromes.

519 003

Thus, the reference syndrome is calculated by multiplying the reference sequence by a parity control matrix for the CRC polynomial and the differential syndromes are calculated as the difference (modulo 2) of the reference sequence blocks and the respective selected block options multiplied by the relevant rows parity control matrix.

In particular, the first decoding means comprise a first shift register and the reference syndrome is calculated by shifting the reference sequence once through said first shift register. The second decoding means are especially implemented as a second shift register with loadable parameters which are given values ​​that are tabulated in the storage means for different positions according to the various alternatives as provided by the error correction means. Differential blocks are then shifted through the second shift register to give the differential syndrome.

Therefore, there is also provided a fault detection device consisting of a CRC decoder. According to the invention, the CRC decoder is differential and comprises first decoding means, second decoding means and storage means as already discussed above.

In addition, a method is provided for detecting errors in a CRC-encoded digital signal. The method includes the steps of dividing the data signal sequence into blocks each comprising a plurality of bits; detecting blocks in the sequence of an error correction decoder where the error correction decoder provides a number of block options for error detecting means. The method further includes the steps of; providing information, such as parameter values, relating to block options, to storage means; storing information on said alternatives in said storage medium; providing the alternatives to a differential error detecting decoder; using a reference sequence in the first decoding means in the differential decoder to produce a reference syndrome;

519 003 decoding differential alternative blocks using the block alternatives and information relating thereto the contents of the storage means by calculating the difference between the reference block and the respective differential blocks to give differential syndrome;

adding a number of (between 1 and N) differential syndromes (not two from the same block position) to the reference syndrome to obtain a respective number of resulting syndromes;

and, if the value of a respective resulting syndrome is zero, a block alternative is accepted.

Particularly advantageous embodiments or alternatives of the subclaims are indicated.

It is an advantage of complicated extension operations. High performance alternative easy calculations are replaced by

The invention may be considerably shorter in that the number of lengths is reduced and thus and thus provide method. The high and simpler calculation is especially advantageous of the invention that one is provided and that the sufficient number can be tested, device a reliable advantage of the invention the calculation operations can be saved power and examples, for example, the number of DSPs; Processor) needed is reduced.

that through

BRIEF DESCRIPTION OF THE DRAWINGS

The invention will be further described hereinafter in a non-limiting manner and with reference to the accompanying figures in which:

Fig. 1A illustrates very schematically how error correction and detection means act on a sequence on the transmitting side;

519 003

<td></td><td>Figure</td><td>IB</td><td>very schematically, as in Fig. 1A, illustrates how error correction and detection means act on a sequence on the receiving side;</td>

<td> 5</td><td>Figure</td><td> 2</td><td>schematically illustrates CRC coding means that can used for the coding procedure,</td>

<td> 10</td><td>Figure</td><td> 3</td><td>schematically illustrates the first CRC decoding means for the decoding procedure of the reference sequence of the invention,</td>

<td> 15</td><td>Figure</td><td> 4</td><td>illustrates the other CRC decoding means for decoding a differential sequence of the invention;</td>

<td></td><td>Figure</td><td> 5</td><td>illustrates an example of a sequence comprising five blocks, therefore three of the blocks of different alternatives are given, there</td>

<td> 20</td><td>Figure</td><td>5A</td><td>shows</td><td>one</td><td>first</td><td>block alternative</td>

<td></td><td>Figure</td><td>5B</td><td>shows</td><td>one</td><td>Other</td><td>option,</td>

<td></td><td>Figure</td><td>5C</td><td>shows</td><td>one</td><td>third</td><td>option,</td>

<td> 25</td><td></td><td></td><td></td><td></td><td></td><td></td>

<td></td><td>Figure</td><td>5D</td><td>shows</td><td>one</td><td>fourth</td><td>option,</td>

<td></td><td>Figure</td><td>5E</td><td>shows</td><td>one</td><td>fifth</td><td>option,</td>

FIG. 6 is a flow chart describing error detection on the receiving side of the invention; and

519 003

FIG. 7 is a flow diagram describing testing of permutations in a branch of the flow described in FIG.

6.

DETAILED DESCRIPTION OF THE INVENTION

Figures 1A and 1B illustrate very schematically the principle of encoding and decoding in two stages, respectively. On the transmitting side, as schematically illustrated in Figure 1A, first error detecting coding means I_TX which act on the entire sequence. Figure 1A first illustrates the uncoded sequence; then illustrates how bits are added at the end (here) for coding purposes; the added bits are shown to follow the dashed line. Thereafter, a separation is performed in K blocks (bits B1-BK). Then, in a second step, an error correction coding means ΙΙ is implemented_Τχ, which apply error correction coding blockwise; compare the last row of Figure 1A which shows added bits at the end of each block.

Figure 1B similarly shows the principle on the receiving side when an error-correcting decoder Irx first decodes the blocks in the total sequence. In the second step, the error-detecting CRC decoder IIrx is applied to check whether the error-correcting decoder has made a wrong decision. As illustrated in the figure, the error detecting decoder acts on the entire sequence. Figure 1B illustrates the block composition separately.

According to the invention, a differential CRC decoder (CRC coding as such will be briefly explained below) is provided which operates at a frequency of, for example, K blocks, of which N blocks have M different alternatives, while the other blocks have only one alternative. According to the invention, the entire sequence need not be multiplied by the parity check matrix H (for example, shifted by a shift register) for M^N option. Instead, shift

519 003 the first option, the reference option, once through the shift register (if shift register is used, which however relates to an advantageous implementation) and then a reference syndrome is calculated as:

So - [p bio b2o · · bko ·. · B (Ki) ob_KO]

hrs_p

hrs_bin

HB2

Hbk

Hb (kl)

Hbk where the dimensions of the matrix are as follows: s (which is a syndrome) has the dimension 1 xm, where m is the order of the CRC polynomial, p (preamble; block beginning) has the dimension 1 xm, b_x (referring to block x) has the dimension 1 xn, where n is the length of a decoded block, H_p has the dimension mxm, where m is the order of the CRC polynomial as referenced above, and Hbx has the dimension nxm, where n is the length of a decoded block as also referred to above.

In addition, the linear properties of the code are used in such a way that differential blocks are calculated as the difference (modulo 2) of the block included in the reference option and the respective block options. Differential syndrome is provided by multiplying the differential blocks by the corresponding portion of the parity control matrix such as:

519 003 &amp; S_k = [Ο Ο Ο. . . Ltd_k . . . OO]

Η_ρ

hrs_inter

HB2

hrs_bk - &amp; b_khrs_bk

hrs_b (N)

hrs_BN

In a particular embodiment, this is implemented by shifting the differential blocks through shift registers (the second shift register referenced above, which has parameters that can be given values ​​according to the contents of storage means as will be discussed further below) to calculate differential syndrome. The new or resultant syndrome is calculated as the sum (modulo 2) of the reference syndrome and the differential (differential) syndrome, respectively. If shift register is used, the second shift register is different for different block positions and allows data to be fed in both directions. The coefficients of the CRC polynomial are used as backward coefficients while the forward feed coefficients consist of individual vectors in the parity control matrix. If an implementation using shift register is applied, the second shift register providing differential blocks b_k have h coefficients according to the bottom row of H_bk. In this way, the shift will be equivalent to the matrix multiplication.

In the following, the concept of CRC coding / decoding will be briefly discussed. CRC bits are used to detect whether a received device can be the same as the transmitted device. If not, the unit is rejected and the transmission is requested to be repeated.

519 003

The CRC code is a block code with a generator polynomial g (x) = 1 + χ⁵+ χ¹²+ χ¹⁶. (This is just one example of your generator polynomial.) One way of realizing the coding is by using shift registers, compare the coding means 10 in Figure 2. As a starting state, the register contains only one which, like the generator polynomial, is specified in ITU-T's ( former CCITT) code standard. (However, any starting state can be used and the invention is not limited to the standard). The vector presentation g of g (x) is [100010000001000]. Then bits are changed and the registered bits are replaced. The decoding is done by shifting the unit consisting of a number of bits through a similarly constructed register. If a block start is implemented, it must be shifted through the register first. This will be discussed further below, see also Figure 3. If the decoding register after the shift operations only contains zeros, the sequence is accepted and the bits are issued. When the CRC coding is performed on the transmitting side, a sequence u is shifted through a shift register as described in Figure 2. The initial state of the cells c (c₀, Ci, ..., c_k= i, c_m-₂, c_m-i) is 1 in each cell. The g factors are defined by the CRC generator polynomial g (x), i.e. g₅ and gi2 is equal to 1, while all others are equal to 0. The factor g₀ is 1 by definition and it is not printed in Figure 2. Thus, the g-factors of the multiplier 2 are used._X, 2₂, . .., 2_m_ !. The CRC code is a systematic block code which means that the information bits remain unchanged, and the control bits are added at the beginning or end. As long as information bits are shifted, they are also fed to the x output. When all bits of information have been processed, a switch 3 switches over and the cell contents are replaced. The encoded sequence x will then be

X = [U_OU1. . . Uend C_m-₂ C_m-₂ . . . C₀]

519 003 because c_m_i is replaced first and Co is last replaced by the registry's permission bits.

The block code with a generating polynomial will be described by a generator matrix G. The generator matrix for a systematic code that encodes k bits to n and adds the control bits at the end assumes the expression:

G (k, n) - [I (k, k) IR (k, n-J

Where the indexes are the sizes of the matrices and I is the identity matrix. In an implementation that uses shift registers, and if the shifting process is to be equivalent to a matrix multiplication, the start states in each register cell must be zero. Otherwise, the shifting process is not linear which is the matrix multiplication. In the CRC coding means of Figure 2, the gi CRC generator polynomial for Xi, u is the uncoded sequence and x is the coded sequence. x includes the original sequence u followed by the contents of the cells as they are replaced by the switch 3 at t = t_sin_out, which corresponds to the time when the entire sequence u has been shifted.

CRC decoding will now be briefly discussed. When a received sequence y is decoded, it is multiplied by the parity check matrix Η. H is defined as:

H (nk, n) ⁼ [R^T (n ^ kfk) In fn k1 where R is the same sub-matrix as in the generator polynomial G. The sequence y can be seen as the modulo-2 sum of the transmitted sequence x and a

519 003 error vector whose element is 1 when an error has occurred and 0 otherwise.

The syndrome s is defined as:

S = [py] H^T = ([px] ® e) H^T = [px] H^T ® eH^T where e is the error vector corresponding to [px]. The bits ie corresponding to p (which is the beginning of the block) are all zero.

The products [px] H^T can be written as:

[Px] H^T = [pu] GH^T =

- [pu] IR (k, nk)]

R (k, nk)

I (nk, nk)

- [pu] (R (k, nk) ® R (k, nk) ') ~ 0 and therefore s = eH^T.

Thus, the syndrome is 0 if all elements ie is 0. If s is different from 0, there is at least one error in the detecting sequence y ·

The calculation of s can be performed in a shift register similar to that used in the coding procedure.

Figure 3 shows a first decoding means 20A used for decoding the reference sequence.

519 003

The factors g are the same as in the coding means, i.e. they represent the CRC generator polynomial. The syndrome is the same as the state of the cells s after replacing all the bits in [py]. The start state bits should all be zeros. This is equivalent to using the p bits in reverse order as a start state and then switching in the received y bits.

The link between a matrix multiplication and a shifting

<td>procedure is that</td><td>the rows in the matrix</td><td colspan="2">hrs^T corresponds</td><td>the states in</td>

<td>the register when a</td><td>only 1 and then only</td><td>0: or</td><td>shifted</td><td>into a plot</td>

<td>register. This</td><td>state sequence</td><td>can</td><td colspan="2">is seen as the registry</td>

<td>impulse response.</td><td></td><td></td><td></td><td></td>

<td>The last line</td><td>i H^T is the same as</td><td>the</td><td>first</td><td>the state of</td>

the impulse response, i.e. when the 1st is shifted. This is so because when the last bit of a sequence is shifted, it will contribute to that state if it is a 1st compared to if it is 0 bit. The final state of the register is the same as the modulo-2 sum of the states generated by the bits being shifted. The shifting operation is thus linear. It is also the matrix multiplication, the product being the same as the modulo-2 sum of the rows in H^T in positions corresponding to ones in the in-vector.

The linear property can be used when analyzing many similar sequences y. If two sequences yi and y₂ with a length of e.g. 130 (which is just one example) and which differ only in some positions between p₀ and (ρο + Δρ-l) should be evaluated to see if either of them generates a zero syndrome, the evaluation of the second sequence can be done quickly by building a new shift register structure. The differential sequence is calculated as:

519 003

Δγ * -ι = yi ® yz and s_y2 = [p y 2] H^T = [p yi] H^r ® [0 Äyjt-1] H^T = - Syl Φ (Awj H rows pO to (pO + Δρ-l) ~ Syl ® As, where Aw is the sequence in Ay_kbetween p₀ and (p₀+ Ap-1). The first term, p_yi, has already been calculated using the shift register in Figure 3. To calculate the second term, a matrix multiplication must be made. This operation needs only the rows po to (po + Ap-1) in H^T. Since only Ap bits are to be shifted into the register, it is unnecessary to use a structure that requires e.g. 13o p_Oshifts must be made to generate the state corresponding to row p₀. It would be advisable to use a register that has impulse response state corresponding to the rows p₀ to (po-Ap-1) in H^T.

This can be achieved by using the other decoding means 20B in Figure 4. The factors h (ho-h_m_i) in the multiplier 6o, ·. , 6_m_i corresponds to row (p₀+ Ap-1) in H^T. After replacing the Aw bits, the As bits are read from the register state. Then y₂syndrome is calculated as:

Sew₂ = Syl Φ AS

If the As corresponding to N Aw is calculated, then 2^N (assuming that there are only two different options for the different positions) different y's are calculated, ie. their syndrome is calculated. In a generalized form this would be M^N, where M is the number of options.

519 003

Thus, the first decoding means 20A (as illustrated in Figure 3) are a shift register decoder for a whole sequence. As referred to above, gi (in the multipliers 2_LR . . . , 2 '1 if the coefficient of xi in the CRC polynomial is 1; 0 otherwise. In the illustrated example, the CRC polynomial of degree m. Y is the sequence that is entered and s1, after completion of the shift, contains the syndrome of the reference sequence. As referred to above, the starting states for all Si are zero. If the initial states Ci for cells 1₀,. . . , l_m-ii the coding means are different from zero (because of the definition in the coding standard), y must be preceded by a block start. The length of the block start is the same as the order m of the CRC polynomial. The block start is defined in such a way that if it is shifted into the coding register, which is initially set to zero, the defined start state must be generated.

Thus, Figure 4 illustrates the other decoding means 20B (which are differential) implemented as a shift register for a separate block,_± corresponds to g in Figure 3, while h is indicated by a row in the CRC polynomial parity check matrix H, depending on blocks, as explained above. Ay is the given differential block and Asi, after completion of the shift, has the corresponding differential syndrome. The starting position here should also contain only zeros. The factors hi are stored in the storage means for each possible block position.

With reference to Figures 5, 5A-5E, an embodiment will be exemplified in which a sequence consists of five blocks B1-B5. In addition, it is assumed that alternatives will be provided for three out of five of these blocks. Figure 5 shows an example of a reference block Y with five blocks corresponding to block positions B1, B2, B3, B4, B5. The reference sequence is assumed to have a first alternative (index 1) in blocks 1, 3 and 4. The reference sequence Y is multiplied

519 003 t

with the parity check matrix H to give a check sum, here referred to as S. As referred to above, this operation can be accomplished by shifting the reference sequence once through the first decoding means, ie. the first shift register 10, once, to provide a reference syndrome S.

Figure 5A shows an alternative sequence in which a second alternative is tested in block position B1, while in block positions B3 and B4 first alternative corresponding to the alternatives in the reference alternative is retained. Thus, the alternative sequence Y needs_A is also multiplied by the parity check matrix H. However, this is done according to the invention by the creation of a differential block ΔΥ_Α in which the difference between alternative in block 1 and the reference alternative in corresponding block is taken, ie. illustrated by BI2-BI1 in block position 1. In the other block positions there are zeros. The differential syndrome AS_Å is then created by multiplying the differential block ΔΥ_Α with the corresponding part of the parity check matrix H, as discussed above. Thus, the new (resultant) syndrome of option Y is given_A such as the sum (modulo 2) of the reference syndrome S and the differential syndrome AS_Å.

In Figure 5B, another alternative is tested in block B3, while blocks B1 and B4 are unchanged. This is indicated by reference Y_B for which index 2 is shown in block B3 illustrating a second alternative for said block. In a manner similar to that discussed with reference to Figure 5A, the differential sequence or differential block is formed by taking the difference between Y_Balternative and the reference alternative, ie B32-B31 in block position 3. In the other block positions, zeros are obtained. This gives a differential syndrome AS_b and the new (resulting) syndrome consists of the sum (modulo

519 003

2) of the reference syndrome and the differential syndrome AS_B such as in Figure 5A.

In Figure 5C an alternative is illustrated in which both blocks B1 and B3 the other alternatives illustrated above are tested at the same time, while there is no change in block position B4 as compared to the reference alternative. This option is called Y_c and, like the previous embodiment, it needs to be multiplied by the parity check matrix H (part thereof). However, in this case, both the alternative in which a second alternative is used in block position B1 (corresponding to Figure 5A) and the alternative in which the second alternative is used in the third block position (B3₂) (corresponding to Figure 5B), already calculated. Therefore, the resulting syndrome is obtained as the sum of the reference alternatives and the differential alternatives ÄS_A and AS_b.

In Figure 5D, a second alternative in block position 4 will be tested corresponding to alternative Y_D. Again comes the differential block B4₂-B4i in position B4 corresponding to ΔΥ₀ to be multiplied by the corresponding part of the H matrix and the new syndrome will be S + AS_D.

Figure 5E relates to another situation in which only one alternative is shown, corresponding to the case when there are three options for block position B1 and the third alternative (illustrated by index 3 in block position B1) is indicated. As before, the first alternatives in block positions B3 and B4 are retained. Here, too, the differential sequence (or differential block BI3-BI1) is shifted by the relevant part of the parity check matrix H, which gives differential syndrome AS_a2and the new syndrome will be S + AS_a2·

519 003

The operations that give the differential syndromes, as referred to above, are fast operations and the relevant parts of the parity control matrix, the h coefficients, are stored in the storage means, such as a table, and the reference syndrome (calculated once) is used in testing each alternative. Thus, it is sufficient that the long operation is done once, while the short operations are done three times, provided that M =

2nd This means that eight different alternatives can be tested using additions (or XOR operations) instead of nine long operations (corresponding to the operation done here once to give the reference syndrome). Since the h coefficients are stored in the storage means, the differential operations can be performed directly. If three alternatives are to be considered for three positions, 27 (3)³) alternatives are tested and yet only a long operation is needed. In addition, six short shift operations and 26 XOR operations are needed to calculate the different combinations.

Figure 6 is a flowchart describing an implementation of the inventive concept. Detected data D is submitted to a fault correction and detection device_IN, which contains sequences each consisting of K blocks, 101. For each block, M decoded alternatives are specified and N blocks are then selected for each of which the M1 alternatives are to be tested which corresponds to the error correction decoding, 102. For the decoded blocks there are thus N positions each containing M alternatives and KN positions with only one alternative. (P_O, Pi, ..., P._N_i denotes the positions of the N blocks that have the most number of options).

A reference sequence is then assembled

103rd Thereafter, the CRC decoding, of all K first alternatives, by any standard method, is applied to the reference sequence which results in a

519 003 Reference Syndrome S, 104, compares the description referring to Figure 3. (The reference sequence may include a block start if such implementation is applicable; however, this is not necessary).

It is then examined whether the reference syndrome corresponds to the O vector. If yes, the reference sequence is OK, 105A, and no further alternatives need to be tested. However, if the reference syndrome is not equal to zero, set to zero, 106. j is equal to 1, 107, and a shift register is formed by input of the appropriate row in H^Tthe matrix corresponding to position Pif where the h coefficients are provided in the storage means, 108. (This procedure was more carefully developed with reference to Figure 4). The differential block is obtained from the relation Abi, j = bi, o^_bi, j, 109. Thereafter, the differential syndrome Asij is calculated using a customized, created disk register decoder on Abifj, 110. Then j is increased by 1, 111, and it is examined if j&gt; M, 112. If not, the next differential is calculated. block (j is increased by 1) and the procedure is repeated from step 109. However, if j&gt; M, i is increased by 1, 113, and it is examined if i&gt; N, 114. If yes, all As are available and permutations should be tested, 214 , which is further discussed in Figure 7. Otherwise, the procedure is repeated from step 108.

In Figure 7, permutations, 214 are tested (compare Figure 6). The number of permutations is set to M^N-1. To begin with, k is equal to 1, 215, and permutation number k is created as, 216:

G (k) (k div (i'M)) toward M; i = 0.1, N-1.

Then the corresponding checksum S is calculated_k according to

519 003

N

SJR ⁼ S + X

2 = 0 with the condition that AS_{I / O} = 0 for each i, 217. Then we examine whether S_k = 0, 218. If yes, S is_k true and a solution has been found, 218A, and no further testing is needed.

About S_k is not equal to 0, k is increased by 1, 219, and it is examined whether 10 k exceeds the number of permutations M^N-1. If not, permutation k + 1 is formed, compare 216 above, and the procedure is repeated. However, if k exceeds the number of permutations, all permutations have been investigated and it is determined that no solution was found, 221.

It should be understood that the invention is not limited to the illustrated embodiments but may be varied in a number of ways within the scope of the appended claims.

519 003