Title of Invention

COMMUNICATION SIGNAL DECODING

Abstract Provided are systems,methods and techniques that use an embedded error-detection code within a received communication signal to determine when to stop iterative decoding of the communication signal.
Full Text FORM 2
THE PATENTS ACT, 1970 (39 of 1970)
&
THE PATENTS RULES, 2003
COMPLETE SPECIFICATION
[See section 10, Rule 13]
COMMUNICATION SIGNAL DECODING;
VIA TELECOM CO. LTD., A COMPANY ORGANIZED AND EXISTING UNDER THE LAWS OF BRITISH WEST INDIES, WHOSE ADDRESS IS ZEPHYR HOUSE, MARY STREET, P.O. BOX 709, GERORGE TOWN, GRAND CAYMAN, CAYMAN ISLANDS, BRITISH WEST INDIES
THE FOLLOWING SPECIFICATION PARTICULARLY DESCRIBES THE INVENTION AND THE MANNER IN WHICH IT IS TO BE PERFORMED.
1

FIELD OF THE INVENTION
The present invention pertains to the decoding of communications signals and is particularly, although not exclusively, applicable to faster turbo decoding at a wireless receiver and to situations in which the format of a received communication signal is not unambiguously known at the receiver.
BACKGROUND
In communication systems, such as illustrated in Figure 1, a transmitter 10 sends information to a receiver 12 via a communication channel 14. Of course, for bidirectional communications between two physically separated units, each unit functions alternately as both a transmitter 10 and a receiver 12.
One problem which any communication system has to address is the potential for loss of information in communication channel 14, e.g., due to fading, noise and other communication channel imperfections. In order to reduce the likelihood of such information loss, it has become common in the design of communications systems to encode digital signals to be transmitted. Such encoding typically involves spreading the information contained in the data bits across a greater number of data bits so that if any are lost the information still potentially can be reconstructed. In practice, it is common to use a type of forward error-correction encoding in which the value of each binary output symbol is formed on the basis of multiple input bits.
Once such information spreading has been completed, the resulting symbols typically are interleaved, so as to ensure that correlated information symbols are not immediately adjacent to each other in the time-domain data stream. By so interleaving, the effects of short-term bursts of noise or fading eventually (after subsequent de-interleaving) are distributed over multiple bits. The end result is that the probability that any particular original information bit cannot be recovered at the receiving end is significantly reduced, meaning more accurate reproduction at the receiving side of the communication channel.
One type of forward error-correction encoding that has become prevalent is turbo coding. A simplified block diagram of a system 20 for implementing one example of turbo coding is illustrated in Figure 2. As shown in Figure 2, input into
2

system 20 is a sequence of information bits 22 to be communicated. Information bits 22 are supplied directly to first constituent encoder 24 and are supplied to second constituent encoder 28 via temporal interleaver 26. Encoders 24 and 28 are identical. Temporal interleaver 26 is a block interleaver, meaning that it interleaves bits in fixed-length segments (or blocks) such that the bits of each such block are interleaved independently of any other block, but with the interleaving pattern typically being identical across all blocks. The precise details of the operation of interleaver 26 and encoders 24 and 28 are not critical to the present invention and therefore are not discussed here. However, each encoder 24 and 28 outputs two symbols for each input bit. Thus, encoder 24 outputs symbols YO and Yl and encoder 28 outputs symbols YO' and Y1’. Output symbol X is identical to the input bit. Accordingly, the X, YO, Yl, YO' and Yl’ symbols (the turbo code) are produced for each input bit.
The turbo code generated in the foregoing manner is first provided to a channel interleaver 30 which interleaves the coded output symbols and sometimes punctures certain of the symbols to insert control signals or other data. Thereafter, the resulting symbols can be processed for transmission, such as by performing quadrature phase-shift keying modulation.
An iterative decoder 50 for decoding the symbols generated by system 20 is illustrated in Figure 3. Initially, channel de-interleaver 52 zeroes any symbols punctured by channel interleaver 30 and then de-interleaves the symbols in order to reverse the interleaving performed by channel interleaver 30. For each input bit k in a frame of data, the received symbols X, Y0 and Y1, together with a feedback signal L(uk), are input into a posteriori probability (APP) decoder 54. On the first iteration
performed by decoder 50, L(uk) is zero for all values of k. Upon completion of its decoding operation, APP decoder 54 outputs a soft value L(uk) for each value of k. L(uk) is then interleaved in interleaver 56 to provide L(un) which in turn is input into APP decoder 58, together with the Y0' and Y1' for the current block. The output of APP decoder 58, L(un), is then de-interleaved in de-interleaver 60. Finally, the output of de-interleaver 60, L(uk), is fed back into APP decoder 54, together with the X, Y0 and Yl
for the current block, for the next iteration of processing to be performed by decoder 50.
The foregoing process typically is repeated across multiple iterations. In
this regard, it is noted that channel de-interleaver 52 makes available all X, Y0, Yl, Y0'
3

and YT for each original input bit in the current block. After every iteration, as
described above, the soft and feedback values L(uk) and L(uk) are added together for
each input bit k in adder 62. The output of adder 62, L(uk), known as the log likelihood
ratio (LLR), is then input into hard decision module 64 to provide a final decision for each bit. Typically, hard decision module 64 is implemented as a threshold detector.
As indicated above, turbo decoding requires multiple iterations of constituent code decoding. In general, using a greater number of iterations results in less decoding error. However, for speed and efficiency it often is desirable to reduce the number of iterations to the extent possible. For a packet of data being decoded, it is advantageous for the decoder to stop iteration when it determines that its performance can no longer be improved by further iterations or when a determination has been made that an error-free decoding already has been achieved.
There have been a number of approaches to determining the appropriate stop criteria when performing iterative decoding. However, each has its own drawbacks.
SUMMARY OF THE INVENTION
The present invention addresses this problem by using an embedded error-detection code within a received communication signal to determine when to stop iterative decoding.
Thus, in one embodiment, the invention is directed to a method of attempting to decode a communication signal, in which a communication signal that includes an embedded error-detection code is received. The communication signal is input into an iterative decoder that decodes the communication signal on an iterative basis, outputting decisions regarding values of the communication signal at each iteration. In addition, at each iteration a measure of error is calculated based on a parameter of the iterative decoder. At each iteration at which the measure of error passes a specified threshold test, a determination is made as to whether there is a detectable error in the decisions based on the embedded error-detection code. Finally, the iterations performed by the iterative decoder are stopped based on both of the following conditions occurring: (i) it is determined that there is no detectable error based on the embedded error-detection code, and (ii) the measure of error passes the specified threshold test. The specified threshold uses a threshold calculated in a predetermined manner based on the embedded error-detection code.
4

In another embodiment, the invention is directed to a method of simultaneously attempting to decode a communication signal and evaluate an assumed transmission format for the communication signal. Initially, a communication signal that includes an embedded error-detection code is received. The communication signal is input into an iterative decoder that decodes the communication signal on an iterative basis, outputting decisions regarding values of the communication signal at each iteration, based on an assumed transmission format. In addition, at each iteration a measure of error is calculated based on a parameter of the iterative decoder. At each iteration at which the measure of error passes a first specified threshold test, a determination is made as to whether there is a detectable error in the decisions based on the embedded error-detection code. The iterations performed by the iterative decoder are stopped and the assumed transmission format is selected based on both of the following conditions occurring: (i) it is determined that there is no detectable error, and (ii) the measure of error passes the first specified threshold test. The iterations performed by the iterative decoder are stopped and the assumed transmission format is de-selected based on the following condition occurring: the measure of error fails a second specified threshold test.
The foregoing summary is intended merely to provide a brief description of the general nature of the invention. A more complete understanding of the invention can be obtained by referring to the claims and the following detailed description of the preferred embodiments in connection with the accompanying figures.
BRIEF DESCRIPTION OF THE DRAWINGS
Figure 1 provides a simplified block diagram of a communication system.
Figure 2 is a block diagram illustrating a conventional turbo encoder.
Figure 3 is a block diagram illustrating a conventional iterative turbo decoder.
Figure 4 illustrates a block diagram of a decoding system according to a representative embodiment of the present invention.
Figure 5 is a flow diagram for explaining iteration-control processing, according to a representative embodiment of the present invention, where the transmission format of the received communication signal is known.
5

Figure 6 illustrates a block diagram of a system for calculating an estimate of bit error rate, according to a representative embodiment of the present invention.
Figure 7 is a graph illustrating the relationship between bit error rate and undetected error rate for three different CRCs.
Figure 8 is a flow diagram for explaining iteration-control processing, according to a representative embodiment of the present invention, where the transmission format of the received communication signal is not unambiguously known.
DESCRIPTION OF THE PREFERRED EMBODIMENT(S)
Figure 4 illustrates a block diagram of a decoding system 80 according to a representative embodiment of the present invention. As shown in Figure 4, a communication signal 81 is received and input by iterative decoder 82. For purposes of the present embodiment, it is assumed that decoder 82 is identical to turbo decoder 50, shown in Figure 3. However, it should be understood that any other iterative decoder instead may be used, depending upon the expected type of encoding for the received communication signal 81.
The output decisions from decoder 82 are provided to error detector 84. As with decoder 82, the nature of error detector 84 will depend upon the expected type of encoding for received communication signal 81. In the preferred embodiments of the invention, communication signal 81 includes an embedded error-detection code. More preferably, the error-detection code is a cyclic redundancy check (CRC) code. Accordingly, in the present embodiment, error detector 84 performs a CRC check on the decoder decisions for each frame provided by decoder 82 in order to determine whether there appears to be a detected error in such frame. It is noted that the term "frame" is used in its generic sense, referring to a data block, segment or packet of a predetermined length.
As noted above, decoder 82 provides decisions at every iteration, generally improving the quality of its decisions with each subsequent iteration. Iteration controller 85, in turn, monitors data from decoder 82 and error detector 84, determining whether a further iteration is required or whether processing on the present frame can be halted, and controlling iterative decoder 82 accordingly. Additional details regarding the
6

functionality provided by controller 85 are discussed in the more particularized embodiments described below.
In this regard, the main categories of embodiments of the present invention are: (i) where the transmission format of the received communication signal 81 is known, so that it is only necessary to decode the communication signal 81, if possible; and (ii) where the transmission format is unknown, so in addition to decoding the communication signal 81, a determination must be made as to which of a plurality of potential transmission formats has been used. As used herein, a transmission format is a set of parameters to form the transmitted data, which may include, e.g., coding rate or other encoding parameters, packet data size, modulation format and/or interleaving parameters.
When a frame-decoding operation according to the present invention is begun, it is provided with data format information (e.g. data packet size, code rate), and inputs information indicating whether such format information is known to be the format in which the data actually were transmitted or is simply a format that has been assumed. If the transmission format is known, the iteration control preferably is executed as described in the section below titled "Known Transmission Format". Otherwise, iteration control preferably is executed as described in the section below titled "Unknown Transmission Format".
Known Transmission Format.
Figure 5 is a flow diagram for explaining iteration-control processing, according to a representative embodiment of the present invention, where the transmission format of the received communication signal 81 is known in advance. Specifically, the processing shown in Figure 5 preferably is performed within iteration controller 85.
Initially, in step 102 controller 85 causes decoder 82 to perform an iteration. Thus, for the initial execution of step 102 this will be the first decoding iteration performed by decoder 82.
Next, in step 103 controller 85 receives one or more decoding parameters for the current iteration from decoder 82, calculates a function of those parameters, and then determines whether the calculated value PQ of the function passes a specified threshold test. Preferably, the calculated value PQ comprises an estimate of bit error rate based on the log likelihood ratio (LLR) magnitudes across all bits in the data packet. As
7

noted above in connection with the discussion of the exemplary decoder 50 illustrated in Figure 3, the LLR is the final value input into hard-decision module 64 of iterative error-correction decoder 50, i.e., L(uk). In the present embodiment, referring to the discussion
below in the section titled "Mathematical Discussion", PQ preferably is calculated as follows:
where K is the number of bits in the data
packet.
A system 110 for calculating P0 is shown in Figure 6. Input into the
system 110 are the L(uk) values, which have been output from adder 62 (shown in Figure 3). Initially, the magnitudes denoted as x are taken in element 112. Then, the
function is performed in element 113, with element 113 preferably implemented
as a lookup table. Next, in element 115 the outputs from element 113 are summed across all A, and then in element 116 a division by K is performed.
Thus, in the preferred embodiments of the invention a threshold test of Po corresponds to a test of the estimated decoding bit error rate. For example, if Po

Documents:

89-mum-2007-abstract.doc

89-mum-2007-abstract.pdf

89-mum-2007-cancelled pages(17-12-2007).pdf

89-mum-2007-claims(granted)-(17-12-2007).doc

89-mum-2007-claims(granted)-(17-12-2007).pdf

89-mum-2007-claims.doc

89-mum-2007-claims.pdf

89-mum-2007-correspondence(17-12-2007).pdf

89-mum-2007-correspondence(ipo)-(02-12-2008).pdf

89-mum-2007-correspondence-received-ver-160107.pdf

89-mum-2007-correspondence-received.pdf

89-mum-2007-description (complete).pdf

89-mum-2007-drawing(17-12-2007).pdf

89-mum-2007-drawings.pdf

89-mum-2007-form 1(16-01-2007).pdf

89-mum-2007-form 18(23-03-2007).pdf

89-mum-2007-form 2(granted)-(17-12-2007).doc

89-mum-2007-form 2(granted)-(17-12-2007).pdf

89-mum-2007-form 3(16-01-2007).pdf

89-mum-2007-form 3(23-03-2007).pdf

89-mum-2007-form 5(16-01-2007).pdf

89-mum-2007-form 9(16-01-2007).pdf

89-mum-2007-form-1.pdf

89-mum-2007-form-2.doc

89-mum-2007-form-2.pdf

89-mum-2007-form-3.pdf

89-mum-2007-form-5.pdf

89-mum-2007-form-9.pdf

89-mum-2007-power of attorney(28-12-2006).pdf

abstract1.jpg


Patent Number 225803
Indian Patent Application Number 89/MUM/2007
PG Journal Number 07/2009
Publication Date 13-Feb-2009
Grant Date 02-Dec-2008
Date of Filing 16-Jan-2007
Name of Patentee VIA TELECOM CO., LTD.
Applicant Address ZEPHYR HOUSE, MARY STREET, P.O.BOX 709, GERORGE TOWN, GRAND CAYMAN
Inventors:
# Inventor's Name Inventor's Address
1 QIANG SHEN 7689 PIPIT PLACE, SAN DIEGO, CA 92129
PCT International Classification Number H04K1/00
PCT International Application Number N/A
PCT International Filing date
PCT Conventions:
# PCT Application Number Date of Convention Priority Country
1 11/559,441 2006-11-14 U.S.A.