Qualitative modeling and compression of request sequences in...

Details Qualitative modeling and compression of request sequences in... Qualitative modeling and compression of request sequences in...

2001-11-13

2003-08-12

JeanPierre, Peguy (Department: 2819)

Coded data generation or conversion

Digital code to digital code converters

C455S352000

Reexamination Certificate

active

06606037

ABSTRACT:

BACKGROUND
1. Field of the Invention
The present invention relates to data compression and, more particularly, to a method and system for compressing the repeat request data in Automatic Repeat reQuest (ARQ) protocols used in telecommunication systems.
2. Description of the Related Art
In many telecommunication systems such as the Universal Mobile Telecommunication System (UMTS), data is transmitted over a communication channel in blocks of predefined sizes. During the transmission, the blocks may become corrupted in spite of various preventive measures and error correction techniques used, such as forward-feed error correction (FEC). Through the use of cyclic redundancy checks (CRC), the corrupted or erroneous blocks can be detected with a high degree of accuracy and reliability. Once the errors are detected, a request for retransmission of the corrupted or erroneous blocks, called a repeat request, may be issued. Issuance of the repeat request is usually done as part of an Automatic Repeat reQuest (ARQ) protocol, which is a common procedure used in modern telecommunication systems, such as UTMS, to recover from erroneous block transmissions.
FIG. 1
is a functional block diagram illustrating an exemplary portion of a typical telecommunication system. As can be seen, the system includes a sender unit
102
that is configured to send blocks of data to a receiver unit
104
over a communication channel
106
. Whenever possible, the sender unit
102
tries to transmit a continuous stream of blocks to the receiver unit
104
. At the receiver unit
104
, the data blocks are verified (e.g., using a CRC) to ensure the data is correctly received. If one or more blocks of data are found to be corrupted or otherwise erroneous, the receiver unit
104
issues a request to the sender unit
102
to retransmit the bad blocks. The repeat request typically includes a series or sequence of bits composed in such a way so as to represent or otherwise indicate which particular blocks need to be retransmitted. Such a request sequence is designated as Rs in FIG.
1
. The timing of the request sequence Rs is usually at regular intervals that may vary in accordance with the system's ARQ protocol.
A number of techniques exist for composing the request sequence Rs. One such technique, called a “list” technique, involves listing the sequence number of the blocks that need to be retransmitted. During normal transmission, each block is assigned one number in a sequence of numbers of a predetermined length. At the receiver end, the sequence number of the block that is corrupted or erroneous is determined, then sent as part of the request sequence Rs to identify the blocks that need to be retransmitted.
Another technique, called a “bitmap” technique, involves using a string of 1s and 0s in the request sequence Rs to identify the blocks that need to be retransmitted. In this technique, a 1 or a 0 is used to denote each block that was received. For example, a 1 may be used to denote a block that has been successfully received and a 0 to denote a block that is erroneous or idle (i.e., no block was received). Thus, a type of bitmap representing the received blocks may be composed with the 0s indicating the blocks that need to be retransmitted.
For very long sequences, however, neither of the above techniques are very practical or economical in terms of bandwidth usage. Therefore, in general, some encoding (compression) of the data in the request sequence Rs is needed.
Data compression can be efficiently performed when certain statistical parameters about the data that is to be compressed are known (e.g., type of data, length of data, generating source). The difficulty with encoding the data in the request sequence Rs, however, is that very little statistical information about the data can be used. For example, although there is a significant amount of correlation between consecutive request sequences, it is uncertain whether one or more of the transmitted sequences will actually be received by the sender unit. Hence, it is usually assumed that there is no correlation between the request sequences Rs (i.e., a decision is made not to use any correlation data). Thus, the probability of any particular combination or distribution of erroneous blocks occurring for a given sequence of transmitted blocks is usually unknown. Due to this lack of knowledge, most presently available algorithms used to compress the ARQ request sequence are “universal,” that is to say, they can adapt their compression scheme to the unknown parameters of a known statistical model of the data or a set of models.
Consider the bitmap approach described above. If no errors occur during the transmission, then the request sequence Rs becomes a binary sequence 111 . . . 100 . . . 0 of a given length N. Any such sequence may be described entirely by its length of n* number of 1s, which is less than or equal to N (that is, n*≦N), and it is sufficient to encode (describe) n* by either a uniform coding (e.g., of length (log
2
N)) or a variable length prefix coding. The advantages of such variable length coding are not clearly obvious and, therefore, if one assumes a uniform coding is used, the result is a compression with a ratio of N/(log
2
N).
If block errors occur, the errors result in the substitution of the continuous run of 1s in the request sequence Rs 11 . . . 100 . . . 0 by a binary sequence x
n
that includes both 1s and 0s mixed together, where n≧n*, but the value of N does not change (that is to say, the length of the run of trailing 0s decreases). The problem, therefore, is to be able to describe the value of n and x
n
using as efficient a coding as possible. The most efficient coding of x
n
, which is a bitmap of the errors, is based on knowing the probability of any/all bitmaps of a given length n occurring. Unfortunately, the probabilities of these bitmaps occurring are usually not known. Sometimes, a known source model (e.g., a two state Markov model), or a rather narrow set of such models, is used for increasing the coding efficiency. This is referred to as “universal” coding. For compression of the request sequence data, however, such universal coding does not work well because the statistical properties of the bitmaps are defined by the statistical properties of the error sequence e
q
=e
1
, . . . , e
n
, where e
i
&egr;{0, 1} and by the ARQ algorithm, and both of these “components” are practically unknown and/or very complex to describe.
In fact, error sequences are “generated” by many sources of many different natures, and their mixture in different proportions defines a very wide class of possible sources. However, even for a small set of source models (or just one model), one cannot translate the statistics of the error sequence into the statistics of the bitmaps. For one thing, the complexity of any ARQ algorithm leaves little chances of solving this problem. Thus, the problem of compressing the request sequence data can be generalized as one of encoding (compressing) the output of a “black box” (i.e., the ARQ algorithm) using input signals (i.e., the error sequence) that are unknown (from the sender's perspective).
Accordingly, it is desirable to be able to provide a method and system for compressing the data in the request sequence of an ARQ algorithm, and to be able to do so in a way that is both computationally efficient and simple to implement.
SUMMARY OF THE INVENTION
The present invention is related to a method and system for compressing the data in the request sequence of an ARQ algorithm. The system and method of the present invention include an entropy encoder module and a probability estimation module. The probability estimation module receives the request sequence from the ARQ algorithm and estimates a probability associated with each symbol or bit in the sequence according to a customized Markov model. The estimated probabilities are thereafter provided to the entropy encoder module, which uses the estimated probabilities to encode each symbol or bit in the request sequence. The

Affiliated with

Also associated with

Rating

Qualitative modeling and compression of request sequences in... does not yet have a rating. At this time, there are no reviews or comments for this patent.

If you have personal experience with Qualitative modeling and compression of request sequences in..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Qualitative modeling and compression of request sequences in... will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFUS-PAI-O-3099403