Abstract:
A voice and data communication system and method for receiving symbols for a plurality of channels into chunks included within buffers, each chunk holding symbols for only a corresponding one of the plurality of channels. As complete frames are received and decoded, the chunks holding the symbols, that are decoded, are freed up to be used for reception of newly arriving symbols included in newly arriving frames.

Description:
BACKGROUND OF THE INVENTION 
     1. Field of the Invention 
     The present invention relates in general to voice and data communications. In particular, the invention pertains to deinterleaving and decoding symbols received over a plurality of channels. 
     2. Description of the Related Art 
     A periodic stream of symbols is received by a deinterleaver and output to a decoder which processes the received symbols. If the deinterleaver deinterleaves the n symbols received during a frame period, then n symbols need to be received by the deinterleaver before being processed by the decoder. A typical bit-reversal deinterleaver would take the n symbols and write them into a two-dimensional table, row by row, and then read the n symbols out column by column, or vice versa. As a result, if the decoder needs to operate on the deinterleaved symbols in order, then typically, the deinterleaver must wait until almost all of the n symbols have been received. Thus, effectively, a periodic stream of symbols must be buffered in one place and then provided to the decoder when the n symbols have been received. 
     While the decoder is processing a buffer of n symbols, more symbols are being received by the deinterleaver. Therefore, the potential exists to overwrite symbols that have not yet been processed by the decoder. Known systems solve this problem by double-buffering the received symbols. 
     FIG. 1 shows a first buffer  10  and a second buffer  20  in a known system for deinterleaving and decoding symbols received during frame periods, n symbols being received during each frame period. Each buffer can store up to n symbols. When the symbols are first received from a deinterleaver  15 , n symbols are stored in, for example, first buffer  10 . After n symbols are received, the n symbols in first buffer  10  are then processed by a decoder  30 . However, while decoder  30  decodes the n symbols, a stream of symbols continues to be received by the deinterleaver. If the symbols are stored in first buffer  10  before the decoder completes processing, then the previously received symbols will be overwritten before being processed. In order to prevent this from occurring, known systems solve this problem by allocating a second buffer  20  to receive n symbols while the decoder processes the n symbols in buffer  10 . Since the process of decoding is faster than the process of receiving symbols from a deinterleaver, by the time n symbols are received and stored in buffer  20 , the decoder is again available and the symbols in buffer  20  can be processed by the decoder while buffer  10  is reallocated to receive another stream of n symbols. 
     SUMMARY OF THE INVENTION 
     The present invention provides a new arrangement for receiving and storing received symbols from a deinterleaver and decoding the received symbols. The system allocates memory for holding the received symbols, such that as symbols are received from a plurality of channels during frame periods, symbols received during previous frame periods for the plurality of channels are decoded, thereby freeing up memory holding the symbols, which have been decoded, to be re-allocated for the reception of new symbols. The system requires less buffer space than a conventional double-buffered system. 
    
    
     BRIEF DESCRIPTION OF THE DRAWINGS 
     FIG. 1 shows a double-buffered system for the reception of symbols from deinterleavers. 
     FIG. 2 shows a system for the reception of symbols from a deinterleaver, which requires less memory for the reception and decoding of frames of symbols. 
     FIG. 3 shows an embodiment of the invention receiving frames of symbols for eight channels, through a deinterleaver. 
     FIG. 4 shows a system for the reception of symbols into buffers, wherein the symbols are stored into chunks within buffers. 
     FIG. 5 shows a preferred embodiment receiving symbols into  6  buffers, each buffer being divided into four chunks. 
     FIG. 6 shows an example of hardware for implementing the scheme described in Table 1. 
    
    
     Table 1 shows an example of buffer allocation as symbols are received for a plurality of channels over a plurality of frames. 
     DETAILED DESCRIPTION OF THE PREFERRED EMBODIMENTS 
     Symbols are received during a time frame or, simply, a frame. Consider, for example, a system which, during a frame, receives n symbols from a deinterleaver  17  every 20 ms. The system has a decoder  30  which takes 10 ms to decode the symbols received during one frame. As illustrated in FIG. 2, after the complete first frame of symbols has been received into, for example, a buffer  12 , which is capable of storing n symbols, the decoder can process the complete frame. During the 10 ms in which the decoder decodes the symbols stored in buffer  12 , n/2 symbols of the next frame are received. These n/2 symbols can be stored in a second buffer  22  which has a capacity to store n/2 symbols. The remaining n/2 symbols of that frame can be stored in the first or second half of buffer  12 . This can be done because the contents of buffer  12  were just decoded and no longer need to be saved. Thus, the system can operate with buffers capable of storing 1.5 frames of n symbols. This is a 25% improvement over known systems that perform double-buffering. 
     If the decoder processing time is different from the example above, then the storage requirement changes. For example, in a system in which frames of symbols are received every 20 ms and the decoder processing time is 15 ms, then while the decoder processes a received frame of n symbols, 15/20*n or 0.75*n symbols are received. These can be received into a second buffer having a capacity of 0.75*n symbols. In this example, the reduction in buffer space is only 12.5% over conventional systems that perform double-buffering. 
     Now consider a system having x channels of symbols simultaneously received and separately processed by the decoder, perhaps serially. For example, as shown in FIG. 3, if eight streams of symbols from eight different channels are separately strobed into the deinterleaver  40 , and buffered by buffers, collectively designated as buffers  60 , but a single decoder  30  is used to process all eight streams in sequence, assuming that a frame is 20 ms, then the decoder must complete processing of each of the eight streams received during the frame in no more than 20/8=2.5 ms. Consequently, then during the first frame, 8 * n symbols are received and stored in eight buffers, each buffer storing n symbols. This can be, for example, buffers B 1 -B 8  of FIG.  4 . Buffer B 1  stores symbols for channel  1 , B 2  for channel  2 , B 3  for channel  3 , etc. While the decoder processes the first channel, n/8 symbols are received for each channel, which can be stored in a ninth buffer, for example, buffer B 9  of size n. However, because the decoder has completed the processing of one frame of symbols for one channel, n memory locations in buffer B 1 , have become free and can then be used for receiving n symbols while the decoder processes the next channel. While the decoder processes the second channel, n/8 symbols are received for each channel and stored in, for example buffer B 1 . Once the decoder is finished with the eighth channel of symbols, stored in B 8 , buffers B 1  through B 7  and B 9  are filled. However, each buffer does not contain a single channel&#39;s symbols. Because the channels were received in n/8 symbol size pieces, or chunks, the data for a channel is contained in eight such chunks, spread across eight buffers. Therefore, at this point, each of buffers B 1  through B 7  and B 9  contain symbols for each of the eight channels, each channel&#39;s symbols being stored in one of the eight chunks of each buffer. As the decoder processes the channels, new symbols will be received and stored into the chunks as they become available. Using this scenario, it would only be necessary to buffer  9 *n symbols of storage, instead of the 16*n that would be required when using double buffering, thereby requiring 43.75% less memory than a double-buffering system. The difficulty here is that the system is actually managing 9*8 or 72 buffers. 
     A “resource allocator” can be used to allocate chunks used for symbol storage. As the decoder completes processing of symbols (either on a per channel basis, or a per chunk basis), it can free up the chunks storing the decoded symbols, so that they may be reused by the resource allocator. If the system uses x channels and n symbols per channel per frame, then x*(x+1) chunks of memory must be available. The resource allocator can utilize an x*(x+1) bit map, in which each bit of 0 indicates a corresponding available chunk, and each bit of 1 indicates a corresponding used chunk. Thus, whenever a chunk is allocated, the first free chunk is provided and its corresponding bit in the bit map is set. Whenever the chunk is freed, its corresponding bit in the bit map is reset to 0. 
     The preferred embodiment supports IS95B, which is a recognized standard. IS95B is described in “TR45 Mobile Station-Base Station Compatibility Standard for Dual-Mode Wideband Spread Spectrum Cellular Systems”, Ballot Version, TLA/EIA/SP-3693 to be known as TIA/EIA-95, Nov. 18, 1997, and is incorporated herein by reference. 
     This embodiment includes a fundamental channel and seven supplemental channels. The fundamental channel takes longer to decode than each of the supplemental channels. A maximum number of eight channels of 384 symbols per frame are received by the deinterleavers. Therefore, for the sake of simplicity, we assume that 384 symbols are received for each channel during a frame. 
     Each decoded channel frees storage space for 384 symbols. If the chunk size is 192 symbols and the buffer size is four chunks, then four buffers, or 16 chunks are required to store eight channels of one frame of symbols. While decoding the fundamental channel, data can be stored into eight additional chunks, but two chunks would free up after decoding a channel. This scheme requires twenty-four chunks of memory, enough to store 4,608 symbols. The actual number of buffers required is six, each having four chunks, as shown in FIG.  5 . 
     Table 1 helps to explain how buffers are allocated using the above scheme. As explained above, each buffer is divided into four chunks, each having a 192 symbol capacity. First, the first half of frame  0 , channels  0 - 3  and  4 - 7  are received, into buffers B 0 ′ and B 1 ′, respectively. That is, the first half of frame  0 , channels  0 - 3  are stored into four chunks, respectively, in buffer B 0 ′ and the first half of frame  0 , channels  4 - 7  are stored into four chunks, respectively, in buffer B 1 ′. 
     Next, the second half of frame  0 , channels  0 - 3  are stored into four chunks, respectively, in buffer B 2 ′ and the second half of frame  0 , channels  4 - 7  are stored into four chunks, respectively, in buffer B 3 ′. After a frame of symbols is completely received, the frame of symbols can be decoded. Therefore, as frame  1  is received, the first half of frame  1 , channels  0 - 3  and  4 - 7  are stored in buffers B 4 ′ and B 5 ′, respectively, while frame  0 , channels  0 - 3  are decoded, freeing up buffers B 0 ′ and B 2 ′. When the second half of frame  1 , is received, the second half of channels  0 - 3  are stored in newly available buffer B 0 ′ and the second half of channels  4 - 7  are stored in newly available buffer B 2 ′. Meanwhile the first and second halves of frame  0 , channels  4 - 7  are decoded, freeing up buffers B 1 ′ and B 3 ′. 
     During frame  2 , the first half frame of symbols for channels  0 - 3  and  4 - 7  are stored in buffers B 1 ′ and B 3 ′, respectively, while the first and second halves of frame  1 , channels  0 - 3  are decoded, freeing up buffers BO′ and B 4 ′. Next, the second half of frame  2 , channels  0 - 3  and  4 - 7  are received into buffers B 4  and B 0 , respectively, while frame  1 , channels  4 - 7  are decoded, freeing up buffers B 2 ′ and B 5 ′. 
     As the first half of frame  3 , channels  0 - 3  and  4 - 7  are received, they are stored in buffers B 5 ′ and B 2 ′, respectively, while frame  2 , channels  0 - 3  are decoded, freeing up buffers B 1 ′ and B 4 ′. When the second half of frame  3 , channels  0 - 3  and  4 - 7  are received, they are stored, respectively, in buffer B 1 ′ and B 4 ′, while frame  2 , channels  4 - 7  are decoded, freeing up buffers B 0 ′ and B 3 ′. 
     As the first half of frame  4 , channels  0 - 3  and  4 - 7  are received, they are stored in buffers B 3 ′ and B 0 ′, respectively, while frame  3 , channels  0 - 3  are decoded, freeing up buffer B 1 ′ and B 5 ′. When the second half of frame  4 , channels  0 - 3  and  4 - 7  are received, they are stored, respectively, in buffers B 5 ′ and B 1 ′, while frame  3 , channels  4 - 7  are decoded, freeing up buffers B 2 ′ and B 4 ′. 
     As the first half of frame  5 , channels  0 - 3  and  4 - 7  are received, they are stored in buffers B 2 ′ and B 4 ′, respectively, while frame  4 , channels  0 - 3  are decoded, freeing up buffer B 3 ′ and B 5 ′. When the second half of frame  5 , channels  0 - 3  and  4 - 7  are received, they are stored, respectively, in buffer B 3 ′ and B 5 ′, respectively, while frame  4 , channels  4 - 7  are decoded, freeing up buffers B 0 ′ and B 1 ′. 
     As the first half of frame  6 , channels  0 - 3  and  4 - 7  are received, they are stored in buffers B 0 ′ and B 1 ′, respectively, while frame  5 , channels  0 - 3  are decoded, freeing up buffers B 2 ′ and B 3 ′. When the second half of frame  6 , channels  0 - 3  and  4 - 7  are received, they are stored, respectively, in buffers B 2 ′ and B 3 ′, while frame  5 , channels  4 - 7  are decoded, freeing up buffers B 4 ′ and B 5 ′. Note that the buffer allocation pattern for frame  6  is a repeat of the pattern for frame  0 , except that the pattern of frame  6  assumes that a previous frame of data was received. 
     As can be seen from examining Table 1, one can easily determine which buffer in which to store the symbols if one maintains a four-bit counter which is incremented, for example, every 10 ms, and if one knows whether the symbols are for channels  0 - 3  or  4 - 7 . 
     Similarly, as can be seen from Table 1, one can easily determine which buffer should be read by the decoder if one maintains a four-bit counter which is incremented, for example, every 10 ms, if one knows whether the symbols are for channels  0 - 3  or  4 - 7 , and if one knows whether to read the first or second half of the frames for the channel set. 
     As illustrated above, one can easily determine which buffer from which to read or to which to write based on knowing the channel set ( 0 - 3  or  4 - 7 ), whether a read or a write operation is to be performed, and whether the first or second half-frames are to be received into buffers or are to be read from buffers. One of ordinary skill in the art would know how to represent Table 1 in a memory device and how to provide an indication of which buffer to access based on the above-mentioned inputs. 
     FIG. 6 is an example of hardware which provides the above information needed to determine from which buffer to read and to which buffer to store the half frames of symbols. For example, counter  71  is a four-bit modulo-12 counter. An enable signal is set every 10 ms to cause the counter  71  to increment every half-frame time period. Thus, counter  71  increments, every 10 ms, within the range of 0-11. The three most significant bits of counter  71  are latched into register  73  every 20 ms, just before counter  71  is incremented. Thus, the register  73  holds the previous frame number. 
     Concatenater  95  receives the three-bit output of register  73 , indicating the frame number. RD-CHANNEL is a one-bit signal from a counter (not shown) used by the decoder to keep track of the channel being decoded. When RD-CHANNEL is 0, channels  0 - 3  are indicated, otherwise, channels  4 - 7  are indicated. RD-SECOND HALF is a one-bit signal from the decoder indicating whether the first or second half of the frame of symbols are to be read. Concatenater  95  receives the three inputs and concatenates them into a five-bit output, which is supplied to multiplexor  75 . When the READ signal, supplied to multiplexor  75  is 1, the output of concatenater  95  is output from multiplexor  75 . 
     Concatenater  93  receives the four-bit signal from counter  71 . A one-bit signal, WR-CHANNEL, is input to concatenater  93  indicating whether the information to be stored pertains to channels  0 - 3  (value 0) or  4 - 7  (value 1). WR-CHANNEL is derived from the most significant bit of a three-bit channel ID number. The two signals are concatenated by concatenater  93  and output as a five-bit signal to multiplexor  75 . Multiplexor  75  outputs the five-bit signal when the READ signal is 0. 
     As can easily be seen, if READ is low, indicating a write operation into a buffer, and if the counter  71  is 0011, and WR-CHANNEL is high or 1, then the output of concatenater  93  indicates frame  1 , second half frame, and channel set  4 - 7 . Thus it can be determined that the second half frame of symbols for channels  4 - 7  in frame  1  are to be stored in buffer  2 ′ (see Table 1). 
     Similarly, assume the register  73  has the value 001, RD-SECOND HALF is high or 1, READ is high, indicating a read operation, and RD-CHANNEL is high. The output of concatenater  95  indicates frame  1 , second half, and channel set  4 - 7 . It can easily be determined that buffer  3 ′ is to be read. 
     Preferably, register  73  of FIG. 6 is a “subtract by 1” block. In this preferred embodiment, the upper three bits of counter  71  enter the “subtract by 1” block and the output of the “subtract by 1” block is simply the input value less 1. However, it is important to note that because the upper three bits of counter  71  are in a range of  0  to  5 , the output of the “subtract by 1” block is in a range of −1 to 4. Therefore, the value −1 in the “subtract by 1” block must be mapped to the value 5. Otherwise this alternate embodiment is identical to that shown in FIG.  6 . 
     While this invention has been described in connection with what is presently considered to be the most practical and preferred embodiments, it is to be understood that the invention is not limited to the disclosed embodiments, but, on the contrary, is intended to cover various modifications and equivalent arrangements included within the spirit and scope of the appended claims. Furthermore, although the invention uses buffers to store symbols, the buffers may be part of a single memory or multiple memories. In addition, the buffers may be included in one or more memories within at least one deinterleaver or separate from the deinterleaver.