Error detection/correction and fault detection/recovery – Pulse or data error handling – Digital data error correction
Reexamination Certificate
1999-10-22
2002-10-22
DeCady, Albert (Department: 2133)
Error detection/correction and fault detection/recovery
Pulse or data error handling
Digital data error correction
C714S758000, C714S784000
Reexamination Certificate
active
06470472
ABSTRACT:
TECHNICAL FIELD
The present invention relates to arrangements, a system and a method within transmission of digital data. At transmission of information, e.g. data communications and wireless communications, errors are substantially always produced when signals are transferred over a channel from the transmitting side to the receiving side. Coding is often used as a protection against distorsion when data is transported over a channel. The present invention particularly relates to a receiving arrangement for receiving a digitally coded data signal transported over a channel. The invention also relates to a system for transferring digitally coded data signals over channels. Still further the invention relates to an error detecting arrangement, particularly a so called CRC (Cyclic Redundancy Check) decoder for detecting errors in a received CRC-coded data signal. The invention also relates to a method of detecting errors in a CRC-coded digital data signal.
One particular case when coding is used as a protection against distorsion is within mobile communications wherein a signal is transferred by radio between a base station and a mobile telephone. The longer the distance, the more the radio signal is attenuated and it also suffers from distorsion in the form of fading produced by interference, so called multiple fading, which means that a signal can take many different ways from one point to another in that it is reflected for example against buildings, etc.
In some digital mobile communication standards coding in two steps has been introduced in order to give an acceptable protection against loss of information. On the transmitting side an error detecting CRC-coder is introduced and as a second step an error correcting block coding device is introduced. A signal is supposed to comprise a number of sequences wherein each sequence is divided into a number of blocks, each of which blocks in turn comprises a number of bits. The error correcting device operates block-wise.
On the receiving side an error correcting decoder which decodes blocks of the total sequence forms a first step. In a second step an error detecting CRC-decoder is implemented to establish whether the error correcting decoder has made any erroneous decisions. The error detecting decoder operates on the entire sequence which, as referred to above, comprises a number of blocks. When the error detecting CRC-decoder detects that the decoded sequence is wrong, it is requested that the sequence be retransmitted. However, this may be very time consuming since several attempts may be necessary. Furthermore, signalling is required between the sending and the receiving side in order to administrate the retransmissions and this demands capacity which otherwise could have been used for useful transmission of information. What is needed is therefore a way to, as fast as possible, find the correct sequence and thus avoid, or at least reduce, retransmission. One known way of handling this problem is to make the error correcting block decoder provide a plurality of alternative suggestions which are tested by the error detecting decoder. The probability that one of the suggestions is correct will then be increased. It is, however, difficult to select candidates. The error correcting decoder is only capable of testing a limited number of alternative solutions. Furthermore, if too many alternatives are tested, the risk increases that an erroneous suggestion is accepted. Alternatives can be selected if each data bit has an attribute in the form of so called soft information, which is a measure on the probability that the chosen sign (zero or one) is correct. Candidates are selected through inverting bits with the lowest soft information, i.e. the bits which are the most likely to be wrong, are questioned first. One method of using soft information is the second algorithm of Chase. This is discussed in “A class of algorithms for decoding block codes with channel measurement information”, IEEE Trans. Inform. Theory, vol. IT-18, pages 170-182, January., 1972, by D. Chase. In “Improved decoding of a concatenated code using soft decoding techniques”, A Master of Science Thesis, dept. of Information Theory, Chalmers University of Technology, Gothenburg, Sweden, by M. Fahami and P. Flodin, December, 1995, the method has been further evaluated. Both these documents are herewith incorporated herein by reference. The soft information method consists in that a number of, for example M, alternatives are calculated for each block in the sequence. A number of blocks, N, are selected out of the total number of blocks. The N blocks should be the poorest blocks as far as this can be concluded, i.e. the blocks relating to which the uncertainty is the highest. The total sequence is then produced and consists of the permutations of the alternatives. Totally, there are thus M
N
alternative sequences to be tested. It should, however, be noted that there are a number of blocks that never have changed (the total sum minus N).
The error detecting CRC-decoder is applied in such a way that the total block decoded sequence is multiplied by the parity check matrix (H) of the CRC-polynomial. This can be realized as the sequence being shifted through a shift register, which e.g. may be implemented as hardware or as software. When the whole sequence has been shifted through the shift register, the content of the shift register is read out. This forms the syndrome of the decoding operation. If the syndrome only comprises zeros, the sequence is accepted, otherwise it is rejected. The CRC-coding can be defined through the original sequence being shifted through a shift register in which the cells have a starting position different from zero. In this manner the shifting operation is made non-linear.
This can, however, be seen as, starting from an initial state in which there are zeros in all cells, a preamble is shifted in which generates the defined starting state and then shifting in the sequence to be coded. On the decoding side this corresponds to the preamble being shifted in first followed by the sequence to be decoded. If a preamble is required, the parity check matrix is increased by as many rows as the preamble comprises. However, the number of the operations is high and, in addition thereto, many shifts are required and such operations are generally long and demanding operations, which in turn reduces the performance or requires much power. A consequence thereof may for example be that less alternatives than actually would be needed are tested.
SUMMARY OF THE INVENTION
What is needed is, therefore, a receiving arrangement for receiving a digitally coded data signal transported over a channel which includes means for error correction and detection, which only requires a limited number of advanced and demanding calculation operations in order to find a correctly transmitted sequence and which particularly requires fewer operations than hitherto known arrangements do. Particularly an arrangement is needed through which it is possible to save power and to lower the fabrication costs. An arrangement is also needed through which a high performance can be provided and through which a correctly transmitted signal efficiently can be found without requiring a high number of demanding operations, much power, etc.
A system for transferring digitally coded data signals over channels from a transmitting side to a receiving side is also needed, through which the above mentioned objects are achieved, i.e. wherein a correctly sent sequence easily and quickly can be found and in which as few retransmissions as possible are needed. An error detecting CRC-decoder for detecting errors in a received CRC-coded digital data signal which has been decoded in error correcting means is also needed, through which the above mentioned objects can be achieved.
Still further, a method of detecting errors in a CRC-coded digital data signal sequence is also needed, through which the detection can be performed fast and in an efficient and reliable manner and requiring as few long and complica
Burns Doane Swecker & Mathis L.L.P.
DeCady Albert
Telefonaktiebolaget LM Ericsson (publ)
Torres Joseph D.
LandOfFree
Arrangements and method relating to transmission of digital... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Arrangements and method relating to transmission of digital..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Arrangements and method relating to transmission of digital... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2999672