Incremental redundancy radio link protocol

Abstract

A method and apparatus for sending blocks of data without any error correcting coding is described. If the block is received without an error then the next block of data is transmitted. If the block is received with an error, the receiving device sends a message requesting error correcting information. The transmitting device sends the error correcting information in specified increments until the receiving device can successfully decode the block without error. Once the block is received without errors, the next block of data is transmitted.

What is claimed is:  
     
         1 . A method for correcting an error in a block of data sent from a first device to a second device, comprising: 
 encoding a block of data by constructing a plurality of data sub-blocks and a plurality of parity sub-blocks;    transmitting only the plurality of data sub-blocks on an initial transmission from the first device to the second device;    determining whether the plurality of data sub-blocks were received with an error; and    if the plurality of data sub-blocks were received with an error: 
 transmitting a first one of the plurality of parity sub-blocks from the first device to the second device.  
   
     
     
         2 . The method of  claim 1 , wherein the plurality of data sub-blocks have no redundancy and represent a 1:1 mapping to the block of data.  
     
     
         3 . The method of  claim 1 , wherein the plurality of parity sub-blocks have parity information derived from the block of data.  
     
     
         4 . The method of  claim 1 , wherein the parity sub-blocks are used by a protocol for forward error correction.  
     
     
         5 . The method of  claim 1 , further comprising: 
 determining whether the transmission of the first one of the plurality of parity sub-blocks enabled successful decoding; and    if the transmission of the first one of the plurality of parity sub-blocks did not enable successful decoding, transmitting subsequent ones of the plurality of parity sub-blocks from the first device to the second device.    
     
     
         6 . The method of  claim 5 , wherein the transmitting of subsequent ones of the plurality of parity sub-blocks occurs in incremental steps.  
     
     
         7 . The method of  claim 6 , wherein each incremental step transmits a succeeding one of the plurality of parity sub-blocks.  
     
     
         8 . The method of  claim 5 , wherein transmitting subsequent ones of the plurality of parity sub-blocks continues until decoding succeeds or all of the plurality of parity sub-blocks have been transmitted.  
     
     
         9 . The method of  claim 1 , further comprising maintaining a table to store an identification of data sub-blocks that have been transmitted from the first device but not yet determined to be received at the second device without an error.  
     
     
         10 . A machine-readable medium having stored thereon a plurality of executable instructions, the plurality of instructions comprising instructions to: 
 encode a block of data by constructing a plurality of data sub-blocks and a plurality of parity sub-blocks;    transmit only the plurality of data sub-blocks on an initial transmission from the first device to the second device;    determine whether the plurality of data sub-blocks were received with an error; and    if the plurality of data sub-blocks were received with an error: 
 transmit a first one of the plurality of parity sub-blocks from the first device to the second device.  
   
     
     
         11 . The machine-readable medium of  claim 10 , further having stored thereon a plurality of executable instructions, the plurality of instructions comprising instructions to: 
 determine whether the transmission of the first one of the plurality of parity sub-blocks enabled successful decoding; and    if the transmission of the first one of the plurality of parity sub-blocks did not enable successful decoding, transmit subsequent ones of the plurality of parity sub-blocks from the first device to the second device.    
     
     
         12 . The machine-readable medium of  claim 10 , further having stored thereon a plurality of executable instructions, the plurality of instructions comprising instructions to maintain a table to store an identification of data sub-blocks that have been transmitted from the first device but not yet determined to be received by the second device without an error.  
     
     
         13 . A receiver, comprising: 
 a quantizer that converts soft-decision information from a layer  1  protocol into a q level representation;    a decoder that decodes the at least the q level representation of the soft decision information to yield a concatenated block of data comprising error detection bits of a frame check sequence and a deliverable data block;    a frame check sequence decoder that computes a frame check sequence of the deliverable data block and indicates to the receiver whether the deliverable data block passed the frame check; and    a deblocking module that de-concatenates the deliverable data block and the frame check sequence.    
     
     
         14 . The receiver of  claim 13 , wherein q is a design parameter that trades off receiver memory requirements against system performance.  
     
     
         15 . The receiver of  claim 13 , wherein, for a q level quantization, the memory requirements at the receiver per bit are given by log 2 q.  
     
     
         16 . The receiver of  claim 13 , wherein the decoder uses a soft decision Viterbi algorithm.  
     
     
         17 . A method of recovering a block of data from a plurality of sub-blocks of data, each sub-block of data identified by at least a block sequence number and a sub-block sequence number, comprising: 
 determining whether a data block identified by the block sequence number of the sub-block was previously successfully decoded, and if not previously successfully decoded:    storing the data of the sub-block at a location identified by the block sequence number and the sub-block sequence number;    passing a set of sub-blocks to a decoder; and    decoding the set of sub-blocks to generate the block of data.    
     
     
         18 . The method of  claim 17 , wherein the set of sub-blocks comprises all sub-blocks stored for the block sequence number.  
     
     
         19 . The method of  claim 17  further comprising: 
 computing a frame check sequence of the block of data; and  
 if the frame check sequence passes, storing the block of data in place of the set of sub-blocks.  
 
     
     
         20 . A computer system comprising a processor and a memory, the memory containing instructions to be executed in accordance with the method of  claim 17 .  
     
     
         21 . A method of decoding a block of data from a plurality of data and parity sub-blocks, wherein the data in the data and parity sub-blocks is in a form of soft decision bits and wherein each sub-block of data is identified by at least a block sequence number and a sub-block sequence number, the method comprising: 
 quantizing the soft decision bits of the one of the data and parity sub-blocks to yield a quantized soft-information sub-block;    storing the quantized soft-information sub-block at a location corresponding to the block sequence number and the sub-block sequence number;    passing all quantized soft-information sub-blocks corresponding to the block sequence number to a decoder; and    decoding, at the decoder, all passed quantized soft-information sub-blocks corresponding to the block sequence number to yield a decoded block.    
     
     
         22 . The method of  claim 14 , further comprising: 
 computing a frame check sequence of the decoded block, and if the frame check sequence passes: 
 storing the decoded block in place of all quantized soft-information sub-blocks corresponding to the block sequence number.