Error detection/correction and fault detection/recovery – Pulse or data error handling – Digital data error correction
Reexamination Certificate
2000-09-05
2003-08-12
Decady, Albert (Department: 2133)
Error detection/correction and fault detection/recovery
Pulse or data error handling
Digital data error correction
Reexamination Certificate
active
06606726
ABSTRACT:
BACKGROUND
The present invention relates to digital communication where the information is transmitted in coded blocks and where coding is used both for error correction and error detection. More particularly, the invention relates to simple ways to reduce the error correcting capability in systems that have already been designed in order to improve on error detecting capability.
In wireless communications, the data to be communicated is typically transmitted in bursts. This is for instance the case for cellular systems like GSM and IS-95, and it is also the case for ad hoc systems, such as BLUETOOTH™, operating in the unlicenced Industrial Scientific and Medical (ISM) band at 2.45 GHz.
For all of these kind of systems, coding is used to enhance the quality of the link. One can distinguish between two different kinds of coding: coding used for error correction and coding used for error detection. Often, both of these types of coding are employed to optimize the performance. The working procedure for the encoder and the decoder when both error correction and error detection are used is as follows. First, k information bits to be sent are encoded for error detection. This step is typically achieved by adding so-called cyclic redundancy check (CRC) bits. The total number of bits can then be represented by k′, where k′-k CRC bits have been added. The k′ bits are then encoded for error correction such that the total number of transmitted bits equals n. This might be done either by encoding the k′ bits into one single codeword consisting of n bits, or it might be done by first dividing the k′ bits into n
s
segments, and then encoding each one of these into codewords of length n
s
. In this way the rate of the complete coding scheme equals k
. It can be seen that the parameter k′ is a design parameter which determines how much of the overall coding is spent on error correction and error detection, respectively. For example, in a BLUETOOTH™-compliant system, a 10-bit header (k=10) is first encoded for error detection by adding 8 CRC bits, so that k′=18. The code used for error detection ensures that the distance between any 18 bit codewords is at least 4 (i.e., at least 4 errors would have to occur before an incorrect header would go undetected). The 18 bits are then encoded for error correction by a (3,1) repetition code. For channel conditions in which the probability of a bit error on the channel, P
b
is on the order of 0.1% (which is a reasonable level for the system to operate in), the probability of incorrectly decoding a packet header becomes very small, and the probability of accepting an erroneous header negligible.
The three repetition-coded bits (corresponding to the same original unencoded bit) together constitute a symbol. A majority decision is used when decoding the symbol, which means that so long as at least two of the three bits are correct, a correct decoding decision can be made. In the following, references to bit errors are intended to refer to errors in individual ones of the three repetition-coded bits.
The operation of the receiver is typically as follows. First error correction is performed in the decoding process. Then, the outcome of the error correction is checked by means of the error detection strategy. In the ideal case, the error correction code makes it possible to correct most of the errors in the received n bit blocks, and in this case the number of retransmissions is reduced significantly. Before the decoded codeword is accepted as correct, it is checked by the outer decoder used for error detection only. In this way, the probability of accepting an erroneous decoded codeword can ideally be made sufficiently small.
In cellular systems, the effect of interference from other users is controlled by means of cell- and frequency-planning, as well as by strict power-control. This enables one to ensure that the system will operate at or near optimal channel conditions, which in turn keeps the number of errors within reasonable values. This effectively means that although an erroneous codeword may sometimes be received, it only contains a small number of errors, so that there is a very high probability that this erroneous codeword will be detected by the code for error detection. Consequently, the probability of having an undetected error can be kept sufficiently small.
The same is not true for ad-hoc networks, such as BLUETOOTH™ Although power control might be implemented in order to counteract the propagation loss, the interference is not under control in such systems. In fact, since it is quite possible for an interfering device to be much closer to the receiver than the intended transmitter is, the signal-to-interference ratio (SIR) can be extremely small (e.g., on the order of −20 dB). Also, for a system operating in an unlicenced band such as the 2.45 GHz band, the interferer need not be another communication device, but can also be a device with a significantly higher output power, such as a microwave oven. Again this can cause the received SIR to be more than 20 dB below the point at which the system is working properly.
Due to the possible presence of a very strong interferer in ad hoc networks, some type of spread spectrum technique is typically employed. There are essentially two ways that a spread spectrum system can mitigate interference: by interference suppression or by interference avoidance. Direct Sequence Spread Spectrum (DSSS) is an example of an interference suppression technique. Here the instantaneously used bandwidth greatly exceeds the information data rate to be communicated. The processing gain (PG) is obtained through the spreading sequence. For a multiple access system based on DSSS to work properly, it is essential that the interfering signal not be too much stronger than the desired one. This is due to the fact that the amount of suppression that it is possible to achieve is limited by the PG. This is described in J. C. Haartsen, “The Bluetooth Radio System,”
IEEE Personal Communications
, vol. 7, No. 1, February 2000.
A multiple access technique that is based on interference avoidance is frequency hopped spread spectrum (FHSS). Unlike the case with DSSS, in FHSS the instantaneous bandwidth is on the same order as the symbol rate. The PG in FHSS is instead obtained by letting the carrier frequency hop over a total bandwidth that greatly exceeds the instantaneous one. Ideally, by making the carrier frequencies orthogonal to each other, a problem occurs only if the same carrier frequency is being used by more than one user at a particular moment in time. In practice, a problem might also occur if the users are transmitting on adjacent carrier frequencies at the same time, although the problem of two users transmitting on the same frequency (so-called co-channel interference) typically is the dominating source of performance degradation. If the different devices are hopping between the different carrier frequencies independent of one another in a pseudo-random fashion, the devices will use different carrier frequencies most of the time and will therefore avoid interfering with one another. A major advantage with the FHSS technique compared to DSSS is that the avoidance principle works even if the devices are transmitting with very different output powers. If the data is transmitted in packets, which typically is the case, this means that only a small fraction of the received packets will contain errors, and the throughput of the system will therefore be very good. For the small fraction of packets that are hit by the presence of an interferer, the large number of bit errors in the received packet makes the error correcting code virtually worthless. For example, the probability of a bit error, P
b
, might very well be on the order of 20-50%. This of course means that the packet will not be correctly decoded, but what is even worse is that unless the code used for error detection is powerful enough, it might not even be detected that the received packet contains
Hed Robert
Meuleman Hante
Wilhelmsson Leif
Burns Doane , Swecker, Mathis LLP
Chase Shelly A
De'cady Albert
Telefonaktiebolaget L M Ericsson (publ)
LandOfFree
Optimization of acceptance of erroneous codewords and... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Optimization of acceptance of erroneous codewords and..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Optimization of acceptance of erroneous codewords and... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3117348