Method and apparatus for recovery of particular bits of received frame

BACKGROUND OF THE INVENTION

I. Field of the Invention

0001The current invention relates to communication. More particularly, the present invention relates to a novel method and apparatus for recovery of particular bits of a corrupted frame.

II. Description of the Related Art

0002Communication systems have been developed to allow transmission of information signals from an origination station to a physically distinct destination station. In transmitting an information signal from the origination station over a communication channel, the information signal is first converted into a form suitable for efficient transmission over the channel. Conversion, or modulation, of the information signal involves varying a parameter of a carrier wave in accordance with the information signal in such a way that the spectrum of the resulting modulated carrier is confined within the channel bandwidth. At the destination station the original message signal is replicated from a version of the modulated carrier received subsequent to propagation over the channel. Such replication is generally achieved by using an inverse of the modulation process employed by the origination station.

0003Furthermore, the conversion is selected in accordance with additional characteristics of the channel, including, but not being limited to, signal-to-noise ratio, fading, time variance, and others known to one skilled in the art. Thus, transmission of an information signal over a wireless communication channel will require different consideration than transmission over a wire-like channel, e.g., coaxial cable, optical cable, and others known to one skilled in the art.

0004Modulation also facilitates multiple-access, i.e., simultaneous transmission, of several signals over a common channel. Multiple-access communication systems often include a plurality of remote subscriber units requiring intermittent service of relatively short duration rather than continuous access to the communication channel.

0005There are several multiple-access communication system techniques, such as time division multiple-access (TDMA), frequency division multiple-access (FDMA), and amplitude modulation (AM) schemes such as amplitude companded single sideband known in the art. Another type of multiple-access spread spectrum system is a code division multiple-access (CDMA) modulation system that conforms to the "TIA/EIA/IS-95 Mobile Station-Base Station Compatibility Standard for Dual-Mode Wide-Band Spread Spectrum Cellular System," hereinafter referred to as the IS-95 standard. The CDMA system supports voice and data communication between users over a terrestrial link. The use of CDMA techniques in a multiple-access communication system is disclosed in <patcit id="pcit0001" dnum="US4901307A"><text>U.S. Patent No. 4,901,307</text></patcit>, entitled "SPREAD SPECTRUM MULTIPLE-ACCESS COMMUNICATION SYSTEM USING SATELLITE OR TERRESTRIAL REPEATERS," and <patcit id="pcit0002" dnum="US5103459A"><text>U.S. Patent No. 5,103,459</text></patcit>, entitled "SYSTEM AND METHOD FOR GENERATING WAVEFORMS IN A CDMA CELLULAR TELEPHONE SYSTEM," both assigned to the assignee of the present invention and incorporated herein by reference.

0006In the above-referenced <patcit id="pcit0003" dnum="US4901307A"><text>U.S. Patent No. 4,901,307</text></patcit>, a multiple-access technique is disclosed allowing a large number of mobile telephone system users, each having a transceiver, communicate through satellite repeaters or terrestrial base stations using CDMA spread spectrum communication signals. In using CDMA communications, the frequency spectrum can be reused multiple times thus permitting an increase in system user capacity. The use of CDMA results in a much higher spectral efficiency than can be achieved using other multiple-access techniques.

0007In general, the transmitted information signal is divided into a number of "frames," each of which includes a specified number of information bits and a number of quality metric bits. Each frame is processed in accordance with a selected modulation scheme, and transmitted over a communication channel. At the destination station, the frame is extracted from the communication channel by demodulation. In order to ascertain integrity of information in the extracted signal, the information bits in the frame are protected by a quality metric derived from the information bits. Such a quality metric may be a parity bit, a cyclic redundancy check (CRC), or any other quality metric known to one skilled in the art. Upon extraction of the signal from the received frame, a quality metric is determined from the extracted information bits and compared with the extracted quality metric. If the two quality metrics match, the frame is considered correctly received. Otherwise, the frame is declared erased.

0008The above-described integrity check works well when all the information bits in the frame are equally important. However, certain applications may use frames with bits grouped into blocks of different importance. An example of a frame of this structure is disclosed in co-pending provisional application serial number <patcit id="pcit0004" dnum="US60175371B"><text>60/175,371</text></patcit>, entitled "Accommodating the WCDMA AMR Data Rates in IS-2000 MC," filed January 10, 2000, assigned to the assignee of the present invention. The Adaptive Multi-Rate (AMR) speech coder groups the information bits into three classes called class A, class B, and class C. In a Wideband Code Division Multiple-access (WCDMA) sytem, each class of bits is sent on a different transport channel with possibly different coding and rate matching. The Class A bits are the most important bits, then the Class B bits, and finally the Class C bits. A WCDMA approach uses an 8-bit CRC and a tailed-off convolutional coding for the Class A bits, no CRC and tailed-off convolutional coding for the Class B bits, and no CRC or convolutional coding for the Class C bits. The Telecommunication Industry Association (TIA) Industry Standard-2000 Multi-Carrier (IS-2000 MC) accommodates the AMR speech coder by forming a single frame comprising all three classes A, B, and C with reverse ordering of the AMR information bit classes so that the last (least important) bit class (Class C) is sent first. Because the flexible-rate puncturing starts from the first encoded and repeated symbols and stops after the necessary number of symbols are punctured, the bits located at the end of the frame are more reliable. Puncturing is a technique that affects bit, or bits, legitimately belonging at certain location in a frame. Thus, for example, in power control puncturing, information bits at certain locations are replaced by power control bits. In another example, interleaving may generate bits exceeding a frame length, and the excess bits are discarded. The frame is encoded by a single, tailed-off convolutional code. A single CRC with a length depending on the number of information bits is determined in accordance with all the information bits. Such a frame is depicted in <figref idref="f0001">FIG. 1. FIG. 1</figref> shows a frame structure 100, in which the information bits within the frame are classified as class A 106, class B 104, and class C 102. The different classes are of different importance. In accordance with the method known in the art, all the information bits are protected by a single CRC 108. The frame also contains tail bits 110. The tail bits 110 do not carry any information, and are all zeros. The tail bits 110 are used to initialize an encoder (not shown) for the next frame. However, if the CRC integrity check fails, all the information bits, regardless of their importance, are unrecoverable.

0009The above description uses a wireless communication system as a particular example of a frame with bits of different importance. One skilled in the art will appreciate that this is for explanatory purposes only because the problem of recovery of particular bits of an erased frame is inherent in any communication system.

0010Because it may be desirable to recover the relatively more important block, or blocks, of bits from an erased frame, there exists a need in the art for an integrity check mechanism allowing recovery of the block, or blocks, of bits from an erased frame.

0011Attention is drawn to the document <patcit id="pcit0005" dnum="US5923679A"><text>US 5 923 679 A</text></patcit> which relates to error detection and correction capability. When a class dividing circuit is supplied with the information code from a voice encoder, according to the definition assigned to the information code by the class divider extremely important class 0 information code is supplied to a CRC calculation circuit and a block coding circuit, the next most important class 1 information code is supplied to a block coding circuit, and the next most important class 2 information code is supplied directly to an interleaving circuit. The CRC calculating circuit obtains error correction information for the class 0 information code supplied from the class dividing circuit, generates data with error detection information appended thereto, and supplies it to a class 0 block coding circuit. The class 0 block coding circuit carries out block coding from the data having error detection information appended and class 0 data.

0012Furthermore attention is drawn to the document <patcit id="pcit0006" dnum="US5666370A"><text>US 5 666 370 A</text></patcit> which relates to an error control coding scheme implemented in low bit rate coders in order to improve their performance in the presence of transmission errors typical of the digital cellular channel. The error control coding scheme exploits the nonlinear block codes (NBCs) for purposes of tailoring those codes to a fading channel in order to provide error protection to the compressed half rate speech data. For a half rate speech codec assumed to have a frame size of 40 ms, the speech encoder puts out a fixed number of bits per 40 ms. These bits are divided into three distinct classes, referred to as Class 1, Class 2 and Class 3 bits. A subset of the Class 1 bits are further protected by a CRC for error detection purposes. The Class 1 bits and the CRC bits are encoded by a rate 1/2 Nordstrom Robinson code with codeword length of 16. The Class 2 bits are encoded by a punctured version of the Nordstrom Robinson code. It has an effective rate of 8/14 with a codeword length 14. The Class 3 bits are left unprotected. The coded Class 1 plus CRC bits, coded Class 2 bits, and the Class 3 bits are mixed in an interleaving array of size 16x17 and interleaved over two slots in a manner that optimally divides each codeword between the two slots. At the receiver the coded Class 1 plus CRC bits, coded Class 2 bits, and Class 3 bits are extracted after de-interleaving.

0013Document <patcit id="pcit0007" dnum="EP0798888A"><text>EP 0798888</text></patcit> discloses in the context of digital speech communication to divide a frame into groups according to subjective importance criteria. A CRC is generated for each class prior to transmission. At the receiving end the CRCs are evaluated and combined to determine a quality measure.

SUMMARY OF THE INVENTION

0014In accordance with the present invention, a method , as set forth in claim 1, and an apparatus , as set forth in claim 3 is provided. Further embodiments are claimed in the dependent claims.

0015The present invention is directed to a novel method and apparatus for recovery of particular bits of a received frame in a communication system.

0016Accordingly, at the origination station a frame of data is formed first by determining an outer quality metric in accordance with a plurality of information bits. Then, at least one inner quality metric is determined in accordance with a group of information bits. The frame comprising at least the plurality of information bits, the outer quality metric, and the at least one inner quality metric is transmitted to the destination station.

0017The destination station first attempts to recover the at least one group of information bits when the outer quality metric indicates that the frame has been received correctly. When the frame has not been received correctly, the at least one group of information bits can still be recovered. The recovery is possible when the inner quality metric corresponding to the at least one group of information bits indicates that the at least one group of information bits in the frame has been received correctly.

BRIEF DESCRIPTION OF THE DRAWINGS

0018The features, objects, and advantages of the present invention will become more apparent from the detailed description set forth below when taken in conjunction with the drawings in which like reference characters identify correspondingly throughout and wherein: <ul id="ul0001" list-style="none" compact="compact"><li><figref idref="f0001"><b>FIG. 1</b></figref> shows a frame structure with groups of bits of different importance protected by a single quality metric;</li><li><figref idref="f0002"><b>FIG. 2</b></figref> is a flowchart of a method using multiple CRC to recover particular bits from a frame of data in accordance with one embodiment;</li><li><figref idref="f0001"><b>FIG. 3</b></figref> shows a frame structure with groups of bits of different importance protected by quality metrics in accordance with one embodiment of the invention; and</li><li><figref idref="f0003"><b>FIG. 4</b></figref> is a simplified block diagram of a circuitry in accordance with one embodiment of the present invention.</li></ul>

DETAILED DESCRIPTION OF PREFERRED EMBODIMENTS

0019<figref idref="f0002"><b>FIG. 2</b></figref> is a flowchart of a method using multiple CRC to recover particular bits from a frame of data in accordance with one embodiment.

0020At step <b>200,</b> information bits to form a frame are received. In one embodiment of the invention, the information bits are produced by an AMR speech coder. Control flow then proceeds to step <b>202.</b>

0021At step <b>202,</b> an outer quality metric is determined in accordance with all the information bits. In one embodiment, the quality metric is a CRC. Control flow then proceeds to step <b>204.</b>

0022At step <b>204,</b> an inner quality metric is determined. As explained, a certain group, or groups, of bits of the information bits in a frame may be considered of higher importance, warranting further protection. Therefore, an additional inner quality metric is determined in accordance with the information bits of each such group. In one embodiment, the inner quality metric is a CRC. In one embodiment, using the information bits produced by an AMR speech coder, one inner CRC protecting one group of bits (class A) is used. Control flow then proceeds to step <b>206.</b>

0023At step <b>206,</b> the frame, comprising the information bits, the inner quality metric, the outer quality metric(s), and tail bits, is formed. In one embodiment, the information bits produced by an AMR speech coder are used, resulting in the frame structure shown in <figref idref="f0001"><b>FIG. 3</b></figref><b>.</b> Control flow then proceeds to step <b>208.</b>

0024At step <b>208,</b> the frame is conveyed from an origination station (not shown) to a destination station (not shown). Step 208 includes any processing of the frame antecedent to the conveyance. One skilled in the art will appreciate that the processing depends on many variables. Such variables include, but are not limited to, the transmission media, i.e., wireless or wire-like; modulation, i.e., code division, frequency division, time division; and other variables known to one skilled in the art. Because the present invention can be used independently of such variables, the processing is not discussed further. In one embodiment, accommodating the AMR speech coder data rates in IS-2000 MC, the processing is performed in accordance with IS-2000 MC. Control flow then proceeds to step <b>210.</b>

0025At step <b>210,</b> the frame is received at the destination station (not shown). Step 210 includes any processing of the frame antecedent to decoding. In one embodiment, accommodating the AMR speech coder data rates in IS-2000 MC, the processing is performed in accordance with IS-2000 MC. Control flow then proceeds to step <b>212.</b>

0026At step <b>212,</b> the frame is decoded. As used in step <b>212,</b> the term "decoded" describes the process of receiving an encoded frame and outputting a signal indicating whether the frame has been correctly received or the frame is erased. The outer quality metric is used in step <b>212.</b> In one embodiment, a decoder (not shown) has no information about the rate at which the frame was transmitted by the origination station (not shown). Therefore, the decoder must also determine at which of several rates the frame has been transmitted by the origination station. A detailed example of such a decoder is disclosed in <patcit id="pcit0008" dnum="US5751725A"><text>U.S. Patent No. 5,751,725</text></patcit>, entitled "METHOD AND APPARATUS FOR DETERMINING THE RATE OF RECEIVED DATA IN A VARIABLE RATE COMMUNICATION SYSTEM," assigned to the assignee of the present invention. A simplified description of an exemplary decoding process in accordance with <patcit id="pcit0009" dnum="US5751725A"><text>US. Patent No. 5,751,725</text></patcit> is provided in reference to <figref idref="f0003"><b>FIG. 4</b></figref><b>.</b> One skilled in the art will appreciate that the description is meant for explanatory purposes only, and any other structure capable of the function described can be utilized. In another embodiment, the decoder has information about the rate at which the frame was transmitted by the origination station. Control flow then proceeds to step <b>214.</b>

0027At step <b>214,</b> the decision of further processing of the frame is made based on a signal indicating whether the frame has been correctly received or erased. If the frame is declared correctly received, the control flow continues in step 216. Otherwise, the control flow continues in step <b>216.</b>

0028At step <b>216,</b> the frame is processed in accordance with the intended application of the frame because all the information bits in the frame has been correctly received. In one embodiment, accommodating the AMR speech coder data rates in IS-2000 MC, the processing is performed by a Multiplex Sublayer in accordance with IS-2000 MC. Control flow then proceeds to step <b>218.</b>

0029At step <b>218,</b> a determination whether a frame contains an inner quality metric is performed. In one embodiment, the determination is performed in accordance with a hypothesis of data rate because the protocol governing frame formation determines what data rates contain inner quality metric. In another embodiment, the frame may contain overhead bits indicating whether the frame contains inner quality metric or not. If the frame does not contain an inner metric, the control flow continues in step <b>220.</b> Otherwise, the flow continues in step <b>222.</b>

0030At step <b>220,</b> the processing of the frame ends, and the frame is discarded.

0031At step <b>222,</b> the frame is processed again with respect to integrity of the group or groups of bits of the frame protected by a corresponding inner quality metric. One embodiment of integrity determination is discussed in detail with reference to <figref idref="f0003"><b>FIG. 4</b></figref><b>.</b> Control flow then proceeds to step <b>224.</b>

0032At step <b>224,</b> the result of integrity determination is tested. If the inner quality metric indicates that integrity of the group of bits is intact, the flow continues in step <b>226.</b> Otherwise, the flow continues in step <b>228.</b>

0033At step <b>226,</b> the group of bits is processed in accordance with the intended function. An example of such processing is passing the group of bits to an AMR vocoder (not shown).

0034At step <b>228,</b> the processing of the frame ends, and the frame is discarded.

0035<figref idref="f0001"><b>FIG. 3</b></figref> shows a frame structure <b>300</b> with groups of bits of different importance protected by quality metrics in accordance with an embodiment of the invention. The frame structure <b>300</b> contains three classes of information bits: class A <b>306,</b> class B <b>304,</b> and class C <b>302.</b> The different classes are of different importance. For the purposes of this discussion, it is assume that class A 306 information bits are more important than class B 304 and class C <b>302</b> bits. All the information bits are protected by an outer CRC <b>310.</b> The more important information bits of class A <b>306</b> are further protected by an inner CRC 308. The frame also contains tail bits <b>312.</b> The tail bits <b>312</b> do not carry any information, and are all zeros. The tail bits <b>312</b> are used to initialize an encoder (not shown) for the next frame.

0036Although the particular embodiment of a frame structure is described as having only one group of bits (class A <b>306)</b> protected by an inner CRC, one skilled in the art will understand that the method can be extended to any number of groups. Thus, if an additional protection of class B <b>304</b> bits were desired, an additional inner CRC (not shown) protecting the class B <b>304</b> bits would be added to the frame structure <b>300.</b>

0037One skilled in the art will appreciate that there are numerous circuit structures that can form the frame structure <b>300.</b> Such a circuit structure may be, e.g., a general-purpose processor, a digital signal processor, a programmable logic array, or any other device designed to perform the functions described herein that is known to one skilled in the art. Furthermore, the processor may receive a set of instructions from a memory coupled to the processor. The memory may be a part of the above-mentioned processor or processors, or be a separate element. The implementation of the memory is a design choice. Thus, the memory can be any medium capable of storing information, e.g., a magnetic disk, a semiconductor integrated circuit, and other storage media known to one skilled in the art.

0038<figref idref="f0003"><b>FIG. 4</b></figref> is a simplified block diagram of a circuitry in accordance with one embodiment of the present invention.

0039A frame outputted by a demodulator <b>402</b> is provided to a multi-rate decoder <b>404,</b> which provides error correction on the frame. The decoder <b>404</b> decodes the data based on a predetermined set of rate hypotheses. In an exemplary embodiment, the decoder <b>404</b> is a multi-rate Viterbi decoder disclosed in <patcit id="pcit0010" dnum="US5710784A"><text>U.S. Patent No. 5,710,784</text></patcit>, entitled "MULTIRATE SERIAL VITERBI DECODER FOR CDMA SYSTEM APPLICATIONS," assigned to the assignee of the present invention.

0040In an exemplary embodiment, the decoder <b>404</b> decodes the frame symbols for each of the possible rates to provide separately decoded frames of data, and stores the decoded frames in buffers <b>406a, 406b, 406c, 406d.</b> Although only four data rates are shown, one skilled in the art will appreciate that the concept is equally applicable to any number of data rates. Outputs of each data buffer <b>406a, 406b,</b> 406c, <b>406d</b> are provided to Rate Detection Algorithm (RDA) logic <b>408.</b>

0041The RDA logic <b>408</b> contains a CRC detector <b>408a.</b> The CRC detector <b>408a</b> determines whether the CRC received in the frame matches the CRC determined from each of the decoded frames of data. The CRC detector <b>408a</b> performs a CRC check for the CRC bits in the four decoded frames to help determine whether the currently received frame was transmitted at the full, half, quarter, or eighth rates. The CRC detector <b>408a</b> provides four check bits, C1, C2, C4, and C8 corresponding to the possible rates.

0042In addition, in one embodiment, the RDA logic <b>408</b> contains a symbol error rate (SER) detector <b>408b.</b> The SER detector <b>408b</b> receives the decoded bits <b>410</b>. The SER detector <b>408b</b> also receives an estimate of the received symbol data from the buffers <b>406a, 406b, 406c, 406d.</b> The SER detector <b>408b</b> re-encodes the decoded bits <b>410,</b> and compares them to the estimate of the received symbol data from the buffers <b>406a, 406b, 406c, 406d.</b> The SER is a count of the number of discrepancies between the re-encoded symbol data and the received symbol data from the buffers <b>406a, 406b, 406c, 406d.</b> Therefore, the SER detector 408b generates four SER values: SER1, SER2, SER4, and SER8. The SER values of different frame rates are normalized to account for the difference in the number of symbols per frame. The SER values help provide a determination of the rate of the current frame and integrity of the frame, in addition to the CRC bits.

0043Furthermore, in one embodiment, the RDA logic <b>408</b> contains a Yamamoto metric detector 408c, which provides a confidence metric in accordance with the difference between the selected path through a trellis and the next closest path through the trellis. While the CRC check is dependent on the bits in each of the four decoded frames, the Yamamoto check is dependent on the frame processing antecedent to decoding. The Yamamoto detector <b>408c</b> provides four Yamamoto values for each of the four possible rates: Y1, Y2, Y4, and Y8.

0044The RDA logic <b>408</b> receives the CRC check bits, SER values, and Yamamoto values from the detectors <b>408a, 408b, 408c,</b> respectively. The RDA logic <b>408</b> then determines at which of the four rates the currently received frame was sent. In accordance with the rate determined by the RDA logic 408, a signal is provided to the decoded frame buffers <b>406a, 406b, 406c, 406d.</b> A particular frame buffer <b>406a, 406b, 406c, 406d</b> outputs the stored frame decoded at the determined rate for further processing, or outputs no frame if an erasure is declared. In an alternate embodiment, the RDA logic <b>408</b> outputs a signal indicative of a frame erasure if an erasure is declared.

0045When the RDA logic <b>408</b> declares a frame erasure, the contents of those frame buffers <b>406a, 406b, 406c, 406d</b> that contain a frame with an inner quality metric is provided to an Inner Quality Metric Processor (IQMP) <b>412.</b> In one embodiment, the function of the IQMP <b>412</b> is similar to the function of the RDA logic <b>408,</b> i.e., receiving decoded frames of data at the possible rates that contain a frame with an inner quality metric, and outputting a signal indicating whether the groups of bits protected by the inner quality metric are intact. In one embodiment, the IQMP <b>412</b> has no information about the rate at which the frame was transmitted by the origination station (not shown). Therefore, the IQMP <b>412</b> must also determine at which of the several rates the frame has been transmitted by the origination station. Consequently, the structure of the IQMP <b>412</b> may advantageously be similar to the RDA logic <b>408.</b> Thus, in one embodiment, the IQMP <b>412</b> contains a CRC detector <b>412a,</b> an SER detector <b>412b,</b> and a Yamamoto metric detector <b>412c,</b> functioning in substantially similar manner as the CRC detector 408a, the SER detector 408b, and the Yamamoto metric detector <b>408c.</b> The CRC detector <b>412a,</b> the SER detector <b>412b,</b> and the Yamamoto metric detector <b>412c</b> operate only on the group of bits of the frame that is protected by the inner quality metric.

0046The IQMP <b>412</b> receives the CRC check bits, SER values, and Yamamoto values from the detectors <b>412a, 412b</b> and <b>412c,</b> respectively. The IQMP <b>412</b> then determines at which of the rates, containing an inner quality metric, was the currently received frame sent. In accordance with the rate determined by the IQMP <b>412,</b> the group of bits decoded at the determined rate is outputted for further processing. Alternatively, the frame is discarded if the IQMP <b>412</b> fails to determine the rate.

0047Though the decoder <b>404,</b> the RDA logic <b>408,</b> and the IQMP <b>412</b> are shown as separate elements, one skilled in the art will appreciate that the physical distinction is made for explanatory purposes only. The decoder <b>404,</b> the RDA logic <b>408,</b> and the IQMP <b>412</b> may be incorporated into single processor accomplishing the above-mentioned processing. Thus, such a processor may be, e.g., a general-purpose processor, a digital signal processor, a programmable logic array, or any other device designed to perform the functions described herein that is known to one skilled in the art. Furthermore, the processor may receive a set of instructions from a memory coupled to the processor. The memory may be a part of the above-mentioned processor or processors, or be a separate element The implementation of the memory is a design choice. Thus, the memory can be any medium capable of storing information, e.g., a magnetic disk, a semiconductor integrated circuit, or any other storage media known to one skilled in the art.

0048The previous description of the preferred embodiments is provided to enable any person skilled in the art to make or use the present invention. The various modifications to these embodiments will be readily apparent to those skilled in the art, and the generic principles defined herein may be applied to other embodiments without the use of the inventive faculty. Thus, the present invention is not intended to be limited to the embodiments shown herein but is to be accorded the widest scope consistent with the appended claims.