EP1237284A1

Error correction decoder for vocoding system

Abstract

The invention relates to a decoder for decoding a received vector encoded in accordance with an (n',k') shortened Golay code characterized by the decoder executing a Conway-Sloane algorithm on the received vector to identify a codeword choice closest to the received vector, the executed Conway-Sloane algorithm utilizing a generator matrix Gm for the shortened Golay code, wherein the generator matrix Gm comprises a modification of the generator matrix G for an (n,k) Golay code, wherein n'<n and k'yk, and wherein the generator matrix G includes a plurality of rows and a plurality of columns, and wherein the modification of the generator matrix G to produce the generator matrix Gm comprises the removal of certain plural ones of both the rows and columns of the genrator matrix G.

EP1237284A1, drawing sheet 1 — Sheet 1 of 53

Term

Term ended

Projected expiry passed 15 December 2017, 8.8 years ago.

8 claims: 1 independent, 7 dependent

1
A decoder for decoding a received vector encoded in accordance with an (n', k') shortened Golay code characterized by the decoder executing a Conway-Sloane algorithm on the received vector to identify a codeword choice clses to the received vector, the executed Conway-Sloane algorithm utilizing a generator matrix G m for the shortened Golay code, wherein the generator matrix G m comprises a modification of a generator matrix G for an (n,k) Golay code, wherein n'<n and k'yk, and wherein the generator matrix G includes a plurality of rows and a plurality of columns, and wherein the modification of the generator matrix G to produce the generator matrix G m comprises the removal of certain plural ones of both the rows and columns of the generator matrix G.

43 paragraphs in 4 sections, as filed

BACKGROUND OF THE INVENTION

Technical Field of the Invention

0001The present invention relates to vocoding systems and, in particular, to a high performance implementation with respect to performing decoding and error estimation processes within an improved multi-band excitation (IMBE) vocoding system.

Description of Related Art

0002The IMBE Vocoding System Additional information on the IMBE vocoding system, as well as other speech communication systems, may be obtained by reference to the following references: <ul id="ul0001" list-style="none" compact="compact"><li>United States Patent No. 5,081,681, entitled "Method and Apparatus for Phase Synthesis for Speech Processing";</li><li>United States Patent No. 5,226,084, entitled "Method for Speech Quantization and Error Correction";</li><li>United States Patent No. 5,247,579, entitled "Methods for Speech Transmission"; and</li><li>United States Patent No. 5,491,772, entitled "Methods for Speech Transmission".</li></ul>

0003The disclosures of these references are incorporated by reference herein.

0004Reference is now made to FIGURE 1 wherein there is shown a block diagram of a transmitter side 10 for an improved multi-band excitation (IMBE) vocoding system. For each 20ms segment of speech (having L harmonics) to be encoded, a quantizer 12 generates a plurality of quantizer values b0 through bL+2. The quantizer value b0 comprises the pitch of the speech segment. The quantizer value b1 comprises the voiced/unvoiced bit vector of the speech segment. The quantizer value b2 comprises the gain of the speech segment. Finally, the quantizer values b3 through bL+2 comprise the remaining spectral amplitudes of the L harmonics of the speech segment.

0005A bit vector prioritization unit 14 of the transmitter side 10 receives the plurality of quantizer values b0 through bL+2 and rearranges them into a set of p prioritized bit vectors u0 through u . p This prioritization is made in accordance with the importance of the bits. In this context, an important bit is one that would cause a large distortion in the reconstructed speech if it were received incorrectly. Each 20ms segment of speech is accordingly compressed to n prioritized bits comprising the bit vectors u0 through up by the bit vector prioritization unit 14.

0006The transmitter side 10 further includes a plurality of forward error correction (FEC) encoders 16 implementing error control codes of differing capabilities to transform the bit vectors u0 through up into encoded vectors v0 through vp. An additional m' parity and/or error correction bits are added by the FEC encoders 16 to the n' prioritized speech bits comprising bit vectors u0 through up to output the encoded vectors v0 through vp. Given the decreasing importance of the speech bits in the bit vectors u0 through up, the error control capabilities provided in the encoded vectors v0 through vp by the FEC encoders 16 correspondingly decrease.

0007In a conventional 6.4 kbps IMBE speech coder such as that standardized for the INMARSAT-M satellite communications system, n'=83, m'=45 and p=7. The bit vectors u0 and u1 are encoded by a first and second FEC encoder 16(1) and 16(2), respectively, each implementing a (24,12) extended Golay code to generate the encoded vectors v0 and v1. The bit vectors u2 through u6 are encoded by a third through seventh FEC encoders 16(3)-16(7), respectively, each implementing a (15,11) Hamming code to generate encoded vectors v2 and v6. The remaining bit vector u7 is not encoded, and is thus passed on as the encoded vector v7.

0008In a 7.1 kbps IMBE speech coder proposed for use in the Ericsson DLMR communications system (see, specifically illustrated in FIGURE 1), two modes of operation are proposed. In the first mode, n'=88, m'=54 and p=6. The bit vector u0 is encoded by a first FEC encoder 16(1) implementing a (19,7) shortened Golay code to generate an encoded vector v0. The bit vector u1 is encoded by a second FEC encoder 16(2) implementing a (24,12) extended Golay code to generate encoded vector v1. The bit vectors u2 and u3 are encoded by a third and fourth FEC encoders 16(3) and 16(4), respectively, each implementing a (23,12) Golay code to generate encoded vectors v2 and v3. Finally, the bit vectors u4 and u5 are encoded by a fifth and sixth FEC encoders 16(5) and 16(6), respectively, each implementing a (15,11) Hamming code to generate encoded vectors v4 and v5. The remaining bit vector u6 is not encoded, and is thus passed on as the encoded vector v6.

0009In the second mode, n'=74, m'=68 and p=6. The bit vector u0 is encoded by a first FEC encoder 16(1) implementing a (19,7) shortened Golay code to generate encoded vector v0. The bit vector u1 is encoded by a second FEC encoder 16(2) implementing an (18,6) shortened Golay code to generate encoded vector v1. The bit vectors u2, u3 and u4 are encoded by a third, fourth and fifth FEC encoders 16(3), 16(4) and 16(5), respectively, each implementing an (18,7) shortened Golay code to generate encoded vectors v2, v3 and v4. Finally, the bit vector u5 is encoded by a sixth FEC encoder 16(6) implementing a (23,12) Golay code to generate encoded vector v5. The remaining bit vector u6 is not encoded, and is thus passed on as the encoded vector v6.

0010For any of the IMBE speech coders, the transmitter side 10 generated encoded vectors v0 through vp are interleaved by an interleaver unit 20, and then modulated by a modulator 22 for transmission (as vector c) over a communications channel 24. An example of such a modulator 22 is any known modulator having an M-ary signal constellation (such as quadrature amplitude modulation (QAM) or phase shift keying (PSK)). The communications channel 24 over which the interleaved and modulated code vectors v0 through vp are transmitted may introduce a number of random and/or burst errors producing interleaved and modulated code vector z.

0011Reference is now made to FIGURE 2 wherein there is shown a block diagram of a receiver side 30 for the improved multi-band excitation (IMBE) vocoding system. An appropriate demodulator 32 is provided for demodulating the communications channel 24 transmitted communication vector z to output on line 34 estimates of the bits within the received code vectors z0 through zp. The demodulator 32 further outputs a corresponding reliability vector r including reliability values for each bit within the received code vectors z0 through zp. The reliability values are indicative of the level of confidence expressed by the demodulator 32 in its estimate of a particular received and demodulated bit. Thus, a larger reliability value within the vector r indicates a higher likelihood of the corresponding bit within the received code vector z being estimated correctly. Demodulators, like that described above, producing bit estimates and reliability values are well known in the art, and thus will not be further described. The received code vectors z and the corresponding reliability vector r are then de-interleaved by a deinterleaver unit 38 to produce the encoded vectors v0 through vp.

0012The receiver side 30 includes a plurality of error control decoders 40 to transform the encoded vectors v0 through vp into bit vectors u0 through up. For example, for the 6.4 kbps IMBE speech coding system, the added forty-five error correction bits within the encoded vectors v0 through v7 are removed to recover the eighty-three prioritized speech bits comprising the bit vectors u0 through u7. With specific reference to the 7.1 kbps IMBE speech coding system implementation illustrated in FIGURE 2, in the first mode, the added fifty-four parity bits within the encoded vectors v0 through v6 are removed to recover the eighty-eight prioritized speech bits comprising the bit vectors u0 through u6. In second mode, on the other hand, the added sixty-eight parity bits within the encoded vectors v0 through v6 are removed to recover the seventy-four prioritized speech bits comprising the bit vectors u0 through u6.

0013The number of bits t which can be corrected by a given code is fixed. For example, for the Hamming code only one bit can be corrected. For the Golay, extended Golay, and shortened Golay codes, on the other hand, three bits can be corrected. The error control decoders 40 receive not only the appropriate ones of the encoded vectors v0 through vp to be decoded, but also their corresponding bit reliability values from the reliability vector r. Any one of a number of decoding techniques known to those skilled in the art may be implemented. For example, the reliability vector r may be ignored and the received vector v decoded using a hard decision decoding method. This decoding technique is a relatively low complexity implementation. Alternatively, the reliability vector r may be used to perform a soft decision type decoding (comprising perhaps errors and erasures decoding) of the received vector v. This decoding technique is a relatively medium complexity implementation. Still further, the reliability vector r may be used to perform a maximum likelihood decoding of the received vector v. This decoding technique is a relatively high complexity implementation. The error control decoders 40 further compute for output in conjunction with the bit vector u the Hamming distance dH between the closest candidate vector (corresponding to the selected output bit vector u) and the received vector v. This Hamming distance identifies the number of places where the bits of the candidate vector and the received vector v differ, thus providing.an error estimate for output along with the bit vector u. It is further recognized at this point that in those implementations where no error control decoder is needed for the encoded vector vp, the encoded vector vp is passed on as the bit vector up.

0014The receiver side 30 further includes a bit vector reconstruction unit 44 which receives the prioritized bit vectors u0 through up, along with the corresponding error estimate information provided by the determined Hamming distances dH, and outputs the plurality of quantizer values b0 through bL+2 relating to the 20ms segment of speech. The Hamming distances dH are processed by the unit 44 as error estimate information to identify the reliability of the prioritized bit vectors u0 through up. If the bit vectors u are deemed reliable, they are used to reconstruct the quantizer values b0 through bL+2 relating to corresponding 20ms segment of speech. Conversely, if the bit vectors u are deemed unreliable, they are discarded and the quantizer values b0 through bL+2 relating to the corresponding 20ms segment of speech are reconstructed by interpolation. The generated quantizer values b0 through bL+2 are then processed by a de-quantizer 46 to generate the speech for output.

0015Use of the Hamming distance dH between the closest candidate vector (corresponding to the selected output bit vector u) and the received vector v as a means for locating potential errors in the decoding operation is not preferred because the calculation tends to discard too much available and important information. It also does not exploit available channel tap estimate information. There is a need then for a better error estimation technique which would preferably implement a Euclidean distance calculation.

Conway-Sloane Decoding

0016In the receiver side 30, because of implementation complexity concerns, each of the error control decoders 40 of the system 10 typically comprises a soft decision decoder (and, in particular, an errors and erasures decoder). Such decoders exploit reliability values (from the reliability vector r) in estimating the transmitted codeword. In the absence of fading, and in the presence of Gaussian noise, the optimal soft decision decoder is the maximum likelihood decoder. It is also typically the best decoder in the presence of fading (assuming a good estimate of the fading is available). For a general block code, however, like those implemented in FIGURE 1, maximum likelihood decoding can be hopelessly complex to implement. Accordingly, the soft decision decoding method is preferably implemented for the decoding process, but a need exists for a less complex maximum likelihood decoding scheme.

0017For the IMBE vocoding systems previously described, the encoders 16 implement in some cases a (24,12) extended Golay code and a (23,12) Golay code. For the special case of the (24,12) extended Golay code and the (23,12) Golay code, a maximum likelihood decoder having a very low complexity has been devised by Conway and Sloane (see, IEEE Trans. Infor. Theory, vol. 32, pp. 41-50, 1986). It is preferable to use the Conway-Sloane decoder for these cases as performance improves with no appreciable increase in processing complexity.

0018For the Conway-Sloane decoding method, the received vector v and its corresponding reliability vector r are combined to produce a modified received vector w. The i-th component of the vector w is given by:<maths id="math0001" num="(1)"><math display="block"><mrow><msub><mrow><mtext>w</mtext></mrow><mrow><mtext>i</mtext></mrow></msub><msub><mrow><mtext> = (1 - 2v</mtext></mrow><mrow><mtext>i</mtext></mrow></msub><msub><mrow><mtext>) r</mtext></mrow><mrow><mtext>i</mtext></mrow></msub></mrow></math><img file="EP1237284A1_D0001.tif" /></maths> where vi is the i-th component of v, and ri is the i-th component or r. Maximum likelihood decoding is now performed on the modified received vector w instead of the received vector r.

0019For an (n,k) binary linear code Λ, let y=(y1,...,yn) denote a codeword in Λ, where y1∈{0,1) and l=1, ..., n. Also, let <maths id="math0002" num=""><math display="inline"><mrow><mover accent="true"><mrow><mtext mathvariant="bold">y</mtext></mrow><mo>¯</mo></mover></mrow></math><img file="EP1237284A1_D0002.tif" /></maths> denote y in antipodal form (+1, -1) with elements:<maths id="math0003" num="(2)"><math display="block"><mrow><msub><mrow><mover accent="true"><mrow><mtext>y</mtext></mrow><mo>¯</mo></mover></mrow><mrow><mtext>1</mtext></mrow></msub><msub><mrow><mtext> = (1 - 2y</mtext></mrow><mrow><mtext>1</mtext></mrow></msub><mtext>)</mtext></mrow></math><img file="EP1237284A1_D0003.tif" /></maths> where l=1,...,n. A maximum likelihood decoder finds a codeword y* such that <maths id="math0004" num=""><math display="inline"><mrow><mover accent="true"><mrow><mtext mathvariant="bold">y</mtext></mrow><mo>¯</mo></mover></mrow></math><img file="EP1237284A1_D0004.tif" /></maths>* is closest to w in Euclidean distance. This is the same as saying that <maths id="math0005" num=""><math display="inline"><mrow><mover accent="true"><mrow><mtext mathvariant="bold">y</mtext></mrow><mo>¯</mo></mover></mrow></math><img file="EP1237284A1_D0005.tif" /></maths>* has the largest inner product which is given by:<maths id="math0006" num="(3)"><math display="block"><mrow><msub><mrow><mtext>w</mtext></mrow><mrow><mtext>1</mtext></mrow></msub><msub><mrow><mover accent="true"><mrow><mtext>y</mtext></mrow><mo>¯</mo></mover></mrow><mrow><mtext>1</mtext></mrow></msub><msub><mrow><mtext>* + w</mtext></mrow><mrow><mtext>2</mtext></mrow></msub><msub><mrow><mover accent="true"><mrow><mtext>y</mtext></mrow><mo>¯</mo></mover></mrow><mrow><mtext>2</mtext></mrow></msub><msub><mrow><mtext>* + ··· + w</mtext></mrow><mrow><mtext>n</mtext></mrow></msub><msub><mrow><mover accent="true"><mrow><mtext>y</mtext></mrow><mo>¯</mo></mover></mrow><mrow><mtext>n</mtext></mrow></msub><mtext>*</mtext></mrow></math><img file="EP1237284A1_D0006.tif" /></maths>

0020Now consider a generator matrix G for the (n,k) binary linear code Λ. It is useful to treat the matrix as having an upper matrix G' and a lower matrix G'' as follows:<maths id="math0007" num=""><img file="EP1237284A1_D0007.tif" /></maths> where G' has k' rows, and G'' has k'' rows. Let Λ' denote the set of codewords yj' generated by G', where j=0, ... , 2k'-1. Also, let yi'' denote a codeword generated by G'', where i=0,...,2k''-1. Then:<maths id="math0008" num="(5)"><math display="block"><mrow><msubsup><mrow><mtext>Λ</mtext></mrow><mrow><mtext>i</mtext></mrow><mrow><mtext>'</mtext></mrow></msubsup><msub><mrow><mtext> = {y"</mtext></mrow><mrow><mtext>i</mtext></mrow></msub><msubsup><mrow><mtext> + y</mtext></mrow><mrow><mtext>j</mtext></mrow><mrow><mtext>'</mtext></mrow></msubsup><msubsup><mrow><mtext>, y</mtext></mrow><mrow><mtext>j</mtext></mrow><mrow><mtext>'</mtext></mrow></msubsup><msup><mrow><mtext> ∈ Λ</mtext></mrow><mrow><mtext>'</mtext></mrow></msup><mtext>}</mtext></mrow></math><img file="EP1237284A1_D0008.tif" /></maths> is called a coset of Λ' in the Λ. The cosets Λi' are disjoint, but their union is equal to the code Λ.

0021It is also noted that comparing the received vector v to the elements of Λi' is equivalent to comparing w * <maths id="math0009" num=""><math display="inline"><mrow><mover accent="true"><mrow><mtext mathvariant="bold">y</mtext></mrow><mo>¯</mo></mover></mrow></math><img file="EP1237284A1_D0009.tif" /></maths><maths id="math0010" num=""><math display="inline"><mrow><mfrac linethickness="0" numalign="left" denomalign="left"><mrow><mtext>"</mtext></mrow><mrow><msub><mrow><mtext></mtext></mrow><mrow><mtext mathvariant="bold">i</mtext></mrow></msub></mrow></mfrac></mrow></math><img file="EP1237284A1_D0010.tif" /></maths> to the elements of Λ', where:<maths id="math0011" num="(6)"><math display="block"><mrow><mtext>w * </mtext><msubsup><mrow><mover accent="true"><mrow><mtext>y</mtext></mrow><mo>¯</mo></mover></mrow><mrow><mtext>i</mtext></mrow><mrow><mtext>"</mtext></mrow></msubsup><msub><mrow><mtext> = {v</mtext></mrow><mrow><mtext>1</mtext></mrow></msub><msubsup><mrow><mover accent="true"><mrow><mtext>y</mtext></mrow><mo>¯</mo></mover></mrow><mrow><mtext>i1</mtext></mrow><mrow><mtext>"</mtext></mrow></msubsup><msub><mrow><mtext>, ···, v</mtext></mrow><mrow><mtext>n</mtext></mrow></msub><msubsup><mrow><mover accent="true"><mrow><mtext>y</mtext></mrow><mo>¯</mo></mover></mrow><mrow><mtext>in</mtext></mrow><mrow><mtext>"</mtext></mrow></msubsup><mtext>}</mtext></mrow></math><img file="EP1237284A1_D0011.tif" /></maths> and where: <maths id="math0012" num=""><math display="inline"><mrow><mover accent="true"><mrow><mtext mathvariant="bold">y</mtext></mrow><mo>¯</mo></mover></mrow></math><img file="EP1237284A1_D0012.tif" /></maths><maths id="math0013" num=""><math display="inline"><mrow><mfrac linethickness="0" numalign="left" denomalign="left"><mrow><mtext>"</mtext></mrow><mrow><msub><mrow><mtext></mtext></mrow><mrow><mtext mathvariant="bold">i</mtext></mrow></msub></mrow></mfrac></mrow></math><img file="EP1237284A1_D0013.tif" /></maths>= (<maths id="math0014" num=""><math display="inline"><mrow><mover accent="true"><mrow><mtext mathvariant="bold">y</mtext></mrow><mo>¯</mo></mover></mrow></math><img file="EP1237284A1_D0014.tif" /></maths><maths id="math0015" num=""><math display="inline"><mrow><mfrac linethickness="0" numalign="left" denomalign="left"><mrow><mtext>"</mtext></mrow><mrow><msub><mrow><mtext></mtext></mrow><mrow><mtext mathvariant="bold">i1</mtext></mrow></msub></mrow></mfrac></mrow></math><img file="EP1237284A1_D0015.tif" /></maths>,···,<maths id="math0016" num=""><math display="inline"><mrow><mover accent="true"><mrow><mtext mathvariant="bold">y</mtext></mrow><mo>¯</mo></mover></mrow></math><img file="EP1237284A1_D0016.tif" /></maths><maths id="math0017" num=""><math display="inline"><mrow><mfrac linethickness="0" numalign="left" denomalign="left"><mrow><mtext>"</mtext></mrow><mrow><msub><mrow><mtext></mtext></mrow><mrow><mtext mathvariant="bold">in</mtext></mrow></msub></mrow></mfrac></mrow></math><img file="EP1237284A1_D0017.tif" /></maths>) is yi'' in antipodal form. Now, the search for y* is organized as. follows: an outer loop executed over yi'', and an inner loop is executed over the elements of Λ'.

0022The generator matrix G for the (24,12) extended Golay code may conveniently be represented as an upper matrix G' :<maths id="math0018" num=""><img file="EP1237284A1_D0018.tif" /></maths> and a lower matrix G'':<maths id="math0019" num=""><img file="EP1237284A1_D0019.tif" /></maths> It is noted that the upper matrix G' has a very simple structure. In fact, Λ' is an even parity code repeated four times. Maximum likelihood decoding of the vector w over Λ' is accomplished by forming six 4-tuple sums (I through VI):<maths id="math0020" num="(9)"><math display="block"><mrow><msub><mrow><mtext>α</mtext></mrow><mrow><mtext>I</mtext></mrow></msub><msub><mrow><mtext> = w</mtext></mrow><mrow><mtext>1</mtext></mrow></msub><msub><mrow><mtext> + w</mtext></mrow><mrow><mtext>2</mtext></mrow></msub><msub><mrow><mtext> + w</mtext></mrow><mrow><mtext>3</mtext></mrow></msub><msub><mrow><mtext> + w</mtext></mrow><mrow><mtext>4</mtext></mrow></msub><msub><mrow><mtext>, . . .,α</mtext></mrow><mrow><mtext>VI</mtext></mrow></msub><msub><mrow><mtext> = W</mtext></mrow><mrow><mtext>21</mtext></mrow></msub><msub><mrow><mtext> + w</mtext></mrow><mrow><mtext>22</mtext></mrow></msub><msub><mrow><mtext> + w</mtext></mrow><mrow><mtext>23</mtext></mrow></msub><msub><mrow><mtext> + w</mtext></mrow><mrow><mtext>24</mtext></mrow></msub></mrow></math><img file="EP1237284A1_D0020.tif" /></maths> If the number of negative αN's is odd, the αN having the smallest magnitude is found and its sign is changed. Now, let:<maths id="math0021" num="(10)"><math display="block"><mrow><msub><mrow><mtext>β</mtext></mrow><mrow><mtext>I</mtext></mrow></msub><msub><mrow><mtext> = sign(α</mtext></mrow><mrow><mtext>I</mtext></mrow></msub><msub><mrow><mtext>), . . .,β</mtext></mrow><mrow><mtext>VI</mtext></mrow></msub><msub><mrow><mtext> = sign(α</mtext></mrow><mrow><mtext>VI</mtext></mrow></msub><mtext>)</mtext></mrow></math><img file="EP1237284A1_D0021.tif" /></maths> and the maximum likelihood codeword is then given by:<maths id="math0022" num="(11)"><math display="block"><mrow><msub><mrow><mtext>(β</mtext></mrow><mrow><mtext>I</mtext></mrow></msub><msub><mrow><mtext>β</mtext></mrow><mrow><mtext>I</mtext></mrow></msub><msub><mrow><mtext>β</mtext></mrow><mrow><mtext>I</mtext></mrow></msub><msub><mrow><mtext>β</mtext></mrow><mrow><mtext>I</mtext></mrow></msub><msub><mrow><mtext>, . . .,β</mtext></mrow><mrow><mtext>VI</mtext></mrow></msub><msub><mrow><mtext>β</mtext></mrow><mrow><mtext>VI</mtext></mrow></msub><msub><mrow><mtext>β</mtext></mrow><mrow><mtext>VI</mtext></mrow></msub><msub><mrow><mtext>β</mtext></mrow><mrow><mtext>VI</mtext></mrow></msub><mtext>)</mtext></mrow></math><img file="EP1237284A1_D0022.tif" /></maths> and the inner product is:<maths id="math0023" num="(12)"><math display="block"><mrow><mtext>p = </mtext><mfenced open="|" close="|"><mrow><msub><mrow><mtext>α</mtext></mrow><mrow><mtext>i</mtext></mrow></msub></mrow></mfenced><mtext> + . . . +</mtext><mfenced open="|" close="|"><mrow><msub><mrow><mtext>α</mtext></mrow><mrow><mtext>VI</mtext></mrow></msub></mrow></mfenced></mrow></math><img file="EP1237284A1_D0023.tif" /></maths> to replace the inner loop of the search.

0023With respect to the outer loop, in order to produce the sums of Equation (9), one hundred twenty-eight modified versions of w need to be computed. By inspection of the lower matrix G'', it is noted that all possible sign combinations of w1 through w4 are produced. The same is true for each of the remaining five 4-tuples except that w12, w16, w20, and w24 do not change sign. In this instance, efficiency is obtained by pre-computing αI through αVI under all sign combinations, and then storing the results in six tables (referred to as σI through σVI). At each step of the outer loop, then, the appropriate entries from the six tables are extracted. To further improve the operational processing of the outer loop, the entries for the six tables are computed in a Gray code ordering so that the current sum is found from the prior sum using a single subtraction instead of three additions/subtractions.

0024To implement the decoding algorithm, the plural yi'' items are ordered in some fashion, and then for every yi'' the 4-tuples are mapped in their Gray code numbers γNi. The table of Gray code numbers is stored within the read only memory (ROM) of the decoder. When w is received, the six sum tables σN are pre-computed. In this example of the (24,12) extended Golay code, the sum tables σI and σII each have sixteen entries, and the remaining sum tables σIII through σVI have eight entries each. The main loop of the process is then executed as follows: <ul id="ul0002" list-style="dash" compact="compact"><li>Let p'=0, i'=0, and δ= (δ1,...,δn) = (0,...,0)</li><li>For i=0 to 127 <ul id="ul0003" list-style="dash" compact="compact"><li>Let αI= σI(γIi), ..., αVI= σVI(YVIi)</li><li>Let p= <maths id="math0024" num=""><math display="inline"><mrow><mfenced open="|" close="|"><mrow><msub><mrow><mtext>α</mtext></mrow><mrow><mtext>I</mtext></mrow></msub></mrow></mfenced></mrow></math><img file="EP1237284A1_D0024.tif" /></maths> + ... + <maths id="math0025" num=""><math display="inline"><mrow><mfenced open="|" close="|"><mrow><msub><mrow><mtext>α</mtext></mrow><mrow><mtext>VI</mtext></mrow></msub></mrow></mfenced></mrow></math><img file="EP1237284A1_D0025.tif" /></maths></li><li>If odd number of negative αN's: <ul id="ul0004" list-style="dash" compact="compact"><li>switch sign of smallest magnitude αN</li><li>let p=p - 2 minN |αN|</li></ul></li><li>Compute βI=sign(αI), ..., βVI=sign(αVI)</li><li>If p>p', let p'=p, i'=i, and δ'=(βIβIβIβI, . . . , βVIβVIβVIβVI)</li></ul></li><li>The maximum likelihood codeword in antipodal form is then:<maths id="math0026" num=""><math display="block"><mrow><mover accent="true"><mrow><mtext>y</mtext></mrow><mo>¯</mo></mover><msub><mrow><mtext>* = (δ</mtext></mrow><mrow><mtext>1</mtext></mrow></msub><msubsup><mrow><mover accent="true"><mrow><mtext>y</mtext></mrow><mo>¯</mo></mover></mrow><mrow><mtext>i1</mtext></mrow><mrow><mtext>"</mtext></mrow></msubsup><msub><mrow><mtext>,···,δ</mtext></mrow><mrow><mtext>n</mtext></mrow></msub><msubsup><mrow><mover accent="true"><mrow><mtext>y</mtext></mrow><mo>¯</mo></mover></mrow><mrow><mtext>in</mtext></mrow><mrow><mtext>"</mtext></mrow></msubsup><mtext>),</mtext></mrow></math><img file="EP1237284A1_D0026.tif" /></maths> or in binary form:<maths id="math0027" num=""><math display="block"><mrow><mtext>y* = </mtext><mfrac><mrow><mtext>1</mtext></mrow><mrow><mtext>2</mtext></mrow></mfrac><mtext> - </mtext><mfrac><mrow><mtext>1</mtext></mrow><mrow><mtext>2</mtext></mrow></mfrac><mover accent="true"><mrow><mtext>y</mtext></mrow><mo>¯</mo></mover><mtext>*,</mtext></mrow></math><img file="EP1237284A1_D0027.tif" /></maths></li></ul> with the corresponding information bits denoted u*. In summary then, y* is the maximum likelihood estimate of the modified received codeword w.

0025The foregoing procedure has been extended for use in decoding (23,12) Golay code. The generator matrix G1 for the (23,12) Golay code is found by removing the first column from the upper matrix G' and lower matrix G'' over Equations (7) and (8), respectively. The foregoing algorithm used for the (24,12) extended Golay code is then also used to decode the modified received vector w. To implement this, a zero is appended to the received vector w. Since the received vector w is nominally antipodal, a zero value is equivalent to an erasure.

0026Use of the Conway-Sloane algorithm in decoding either the (24,12) extended Golay code or the (23,12) Golay code provides a marked improvement over the use of other known techniques (especially those implementing a "brute force" searching approach). It is noted, however, that the receiver side 30 in may IMBE speech coding systems (for example, the 7.1 kbps IMBE speech coding system) includes a number of individual error control decoders 40 which must decode various shortened Golay codes such as the (19,7) Golay code, the (18,7) Golay code, and the (18,6) Golay code. Currently, decoding algorithms not as efficient as the Conway-Sloane algorithm (such as those comprising errors and erasures decoders) are being used to implement the necessary decoding operations for these shortened Golay codes. There would be an advantage, however, if the efficient Conway-Sloane algorithm could be extended for use in connection with the decoding of such shortened Golay codes.

0027The closes prior art includes Hardwick et al., U.S. Patent No. 5,517,511 and Forney, U.S. Patent No. 4,933,956. Hardwick discloses a method and apparatus for preserving the quality of speech or other accoustic signals when transmitted over a noisy channel. Hardwick does this through the use of Hamming code and (12,12) Golay code. Forney discloses a two stage decoder for selecting a codeword near to a given N-tuple r, which is a sequence of N real values ri representing signals.

SUMMARY OF THE INVENTION

0028To address the foregoing need with respect to the computation of an improved error estimate for a decoded bit vector, an error control decoder of the present invention receives a received vector to be decodes. The decoder processes calculates, as the error estimate, the Euclidean distance between a codeword choice and the received vector. The output error estimate is appropriately scaled and quantized in accordance with the particular code being implemented by the decoder.

0029To address the foregoing object with respect to the extension of the efficient Conway-Sloane algorithm for use in connection with the decoding of shortened Golay codes, the present invention (claim 1) modifies the generator matrix for the Golay code to produce a modified generator matrix that is specific for and tailored to the decoding of each shortened code. The modified generator matrix is then efficiently implemented in the Conway-Sloane algorithm to identify the best codeword for conversion to its corresponding information bits for output. In particular, the modified generator matrix comprises the Golay code generator matrix with specially chosen rows and columns deleted.

BRIEF DESCRIPTION OF THE DRAWINGS

0030A more complete understanding of the method and apparatus of the present invention may be acquired by reference to the preceding Background of the Invention and the following Detailed Description when taken in conjunction with the accompanying Drawings wherein: <ul id="ul0005" list-style="none" compact="compact"><li>FIGURE 1 is a block diagram of a transmitter side for an improved multi-band excitation (IMBE) vocoding system;</li><li>FIGURE 2 is a block diagram of a receiver side for the improved multi-band excitation (IMBE) vocoding system;</li><li>FIGURE 3 is a block diagram of a decoder of the present invention implementing the Conway-Sloane algorithm for decoding shortened Golay encoded information; and</li><li>FIGURE 4 is a block diagram of a decoder of the present invention implementing a Euclidean distance based error estimation determination.</li></ul>

DETAILED DESCRIPTION OF THE INVENTION

0031Referring now to FIGURE 3, wherein there is shown a block diagram of a decoder of the present invention, the Conway-Sloane technique is extended for use by appropriate ones of the decoders 40 in decoding (19,7) shortened Golay code encoded vectors. The generator matrix G for the (24,12) extended Golay code is manipulated to produce a modified generator matrix G2 100 for use in decoding the (19,7) extended Golay code. In particular, columns twenty, twenty-one, twenty-two, twenty-three and twenty-four are removed from the generator matrix G, and only rows one, two, three, six, seven, eight and nine of the generator matrix G are kept. As a result, the generator matrix G2 for the (19,7) extended Golay code may conveniently be represented as an upper matrix G2' :<maths id="math0028" num=""><img file="EP1237284A1_D0028.tif" /></maths> and a lower matrix G2'' :<maths id="math0029" num=""><img file="EP1237284A1_D0029.tif" /></maths> Three processing efficiencies are encountered with respect to the use of the generator matrix G2 for the (19,7) extended Golay code in the Conway-Sloane algorithm. First., since the last three columns in the upper matrix G2' are zero, only the first four sum tables σN 102 need to be pre-computed and stored in response to the received vector w. Second, since the lower matrix G2'' shares the first four rows of the lower matrix G'', the loop size for the algorithm becomes sixteen instead of one hundred twenty-eight. Third, only the even entries in the four sum tables σN are actually used by the algorithm, and thus need to be pre-computed and stored. Gray code values 104 are also stored.

0032The Conway-Sloane algorithm is then executed 106 on the received vector w (or vector v) in view of the generator matrix G2. The main loop of the process is executed as follows: <ul id="ul0006" list-style="dash" compact="compact"><li>Let p'=0, i'=0, and δ=(δ1, ..., δn) = (0, ..., 0)</li><li>For i=0, 8, 16, ..., to 120 <ul id="ul0007" list-style="dash" compact="compact"><li>Let αI= σI (γIi),..., αIV= σIV(γIVi)</li><li>Let p= <maths id="math0030" num=""><math display="inline"><mrow><mfenced open="|" close="|"><mrow><msub><mrow><mtext>α</mtext></mrow><mrow><mtext>I</mtext></mrow></msub></mrow></mfenced></mrow></math><img file="EP1237284A1_D0030.tif" /></maths> + ... + <maths id="math0031" num=""><math display="inline"><mrow><mfenced open="|" close="|"><mrow><msub><mrow><mtext>α</mtext></mrow><mrow><mtext>IV</mtext></mrow></msub></mrow></mfenced></mrow></math><img file="EP1237284A1_D0031.tif" /></maths></li><li>If odd number of negative αN's: <ul id="ul0008" list-style="dash" compact="compact"><li>switch sign of smallest magnitude αN</li><li>let p=p - 2 minn | αN|</li></ul></li><li>Compute βI=sign(αI), ..., βIV=sign(αIV)</li><li>If p>p', let p'=p, i'=i, and δ' = (βIβIβIβI, ..., βIVβIVβIVβIV,+1,+1,+1)</li></ul></li><li>The maximum likelihood codeword in antipodal form is then:<maths id="math0032" num=""><math display="block"><mrow><mover accent="true"><mrow><mtext>y</mtext></mrow><mo>¯</mo></mover><msub><mrow><mtext>* = (δ</mtext></mrow><mrow><mtext>1</mtext></mrow></msub><msubsup><mrow><mover accent="true"><mrow><mtext>y</mtext></mrow><mo>¯</mo></mover></mrow><mrow><mtext>i1</mtext></mrow><mrow><mtext>"</mtext></mrow></msubsup><msub><mrow><mtext>,···,δ</mtext></mrow><mrow><mtext>n</mtext></mrow></msub><msubsup><mrow><mover accent="true"><mrow><mtext>y</mtext></mrow><mo>¯</mo></mover></mrow><mrow><mtext>in</mtext></mrow><mrow><mtext>"</mtext></mrow></msubsup><mtext>),</mtext></mrow></math><img file="EP1237284A1_D0032.tif" /></maths> or in binary form:<maths id="math0033" num=""><math display="block"><mrow><mtext>y* = </mtext><mfrac><mrow><mtext>1</mtext></mrow><mrow><mtext>2</mtext></mrow></mfrac><mtext> - </mtext><mfrac><mrow><mtext>1</mtext></mrow><mrow><mtext>2</mtext></mrow></mfrac><mover accent="true"><mrow><mtext>y</mtext></mrow><mo>¯</mo></mover><mtext>*,</mtext></mrow></math><img file="EP1237284A1_D0033.tif" /></maths></li></ul> with the corresponding information bits denoted u*. In summary then, y* is the maximum likelihood estimate of the modified received codeword w.

0033Referring again to FIGURE 3, in accordance with the present invention, the Conway-Sloane technique is extended for use appropriate ones of the decoders 40 in decoding (18,6) shortened Golay code encoded vectors. The generator matrix G for the (24,12) extended Golay code is manipulated to produce a modified generator matrix G3 100 for use in decoding the (18,6) extended Golay code. In particular, columns sixteen, twenty, twenty-one, twenty-two, twenty-three and twenty-four are removed from the generator matrix G, and only rows one, two, six, seven, eight and nine of the generator matrix G are kept. As a result, the generator matrix G3 for the (18,6) extended Golay code may conveniently be represented as an upper matrix G3' :<maths id="math0034" num=""><img file="EP1237284A1_D0034.tif" /></maths> and a lower matrix G3'':<maths id="math0035" num=""><img file="EP1237284A1_D0035.tif" /></maths> Three processing efficiencies are encountered with respect to the use of the generator matrix G3 for the (18,6) extended Golay code in the Conway-Sloane algorithm. First, since the last six columns in the upper matrix G3' are zero, only the first three sum tables σN 102 need to be pre-computed and stored in response to the received vector v. Second, since the lower matrix G3'' shares the first four rows of the lower matrix G'', the loop size for the algorithm becomes sixteen instead of one hundred twenty-eight. Third, only the even entries in the four sum tables σN are actually used by the algorithm, and thus need to be pre-computed and stored. Gray code values 104 are also stored.

0034The Conway-Sloane algorithm is then executed 106 on the modified received vector w (or received vector v) in view of the generator matrix G3. The main loop of the process is executed as follows: <ul id="ul0009" list-style="dash" compact="compact"><li>Let p'=0, i'=0, and δ=(δ1,...,δn)=(0,...,0)</li><li>For i=0, 8, 16, ..., to 120 <ul id="ul0010" list-style="dash" compact="compact"><li>Let αI= σI(γIi),.., αIII= σIII(γIIIi)</li><li>Let p= <maths id="math0036" num=""><math display="inline"><mrow><mfenced open="|" close="|"><mrow><msub><mrow><mtext>α</mtext></mrow><mrow><mtext>I</mtext></mrow></msub></mrow></mfenced></mrow></math><img file="EP1237284A1_D0036.tif" /></maths> + ... + <maths id="math0037" num=""><math display="inline"><mrow><mfenced open="|" close="|"><mrow><msub><mrow><mtext>α</mtext></mrow><mrow><mtext>III</mtext></mrow></msub></mrow></mfenced></mrow></math><img file="EP1237284A1_D0037.tif" /></maths></li><li>If odd number of negative αN's: <ul id="ul0011" list-style="dash" compact="compact"><li>switch sign of smallest magnitude αN</li><li>let p=p - 2 minN | αN|</li></ul></li><li>Compute βI=sign(αI), ..., βIII=sign(αIII)</li><li>If p>p', let p'=p, i'=i, and δ' = (βIβIβIβI,..., βIIIβIIIβIIIβIII, +1,...,+1)</li></ul></li><li>The maximum likelihood codeword in antipodal form is then:<maths id="math0038" num=""><math display="block"><mrow><mover accent="true"><mrow><mtext>y</mtext></mrow><mo>¯</mo></mover><msub><mrow><mtext>* = (δ</mtext></mrow><mrow><mtext>1</mtext></mrow></msub><msubsup><mrow><mover accent="true"><mrow><mtext>y</mtext></mrow><mo>¯</mo></mover></mrow><mrow><mtext>i1</mtext></mrow><mrow><mtext>"</mtext></mrow></msubsup><msub><mrow><mtext>,···,δ</mtext></mrow><mrow><mtext>n</mtext></mrow></msub><msubsup><mrow><mover accent="true"><mrow><mtext>y</mtext></mrow><mo>¯</mo></mover></mrow><mrow><mtext>in</mtext></mrow><mrow><mtext>"</mtext></mrow></msubsup><mtext>),</mtext></mrow></math><img file="EP1237284A1_D0038.tif" /></maths> or in binary form:<maths id="math0039" num=""><math display="block"><mrow><mtext>y* = </mtext><mfrac><mrow><mtext>1</mtext></mrow><mrow><mtext>2</mtext></mrow></mfrac><mtext> - </mtext><mfrac><mrow><mtext>1</mtext></mrow><mrow><mtext>2</mtext></mrow></mfrac><mover accent="true"><mrow><mtext>y</mtext></mrow><mo>¯</mo></mover><mtext>*,</mtext></mrow></math><img file="EP1237284A1_D0039.tif" /></maths></li></ul> with the corresponding information bits denoted u*. In summary then, y* is the maximum likelihood estimate of the modified received codeword w.

0035Referring again to FIGURE 3, in accordance with the present invention, the Conway-Sloane technique is extended for use appropriate ones of the decoders 40 in decoding (18,7) shortened Golay code encoded vectors. The generator matrix G for the (24,12) extended Golay code is manipulated to produce a modified generator matrix G4 100 for use in decoding the (18,7) extended Golay code. In particular, columns one, twenty, twenty-one, twenty-two, twenty-three and twenty-four are removed from the generator matrix G, and only rows one, two, three, six, seven, eight and nine of the generator matrix G are kept. As a result, the generator matrix G4 for the (18,7) extended Golay code may conveniently be represented as an upper matrix G4':<maths id="math0040" num=""><img file="EP1237284A1_D0040.tif" /></maths> and a lower matrix G4'':<maths id="math0041" num=""><img file="EP1237284A1_D0041.tif" /></maths> Three processing efficiencies are encountered with respect to the use of the generator matrix G4 for the (18,7) extended Golay code in the Conway-Sloane algorithm. First, since the last three columns in the upper matrix G4' are zero, only the first four sum tables σN 102 need to be pre-computed and stored. Second, since the lower matrix G4'' shares the first four rows of the lower matrix G'', the loop size for the algorithm becomes sixteen instead of one hundred twenty-eight. Third, only the even entries in the four sum tables σN are actually used by the algorithm, and thus need to be pre-computed and stored. Gray code values 104 are also stored.

0036The Conway-Sloane algorithm is then executed 106 on the modified received vector w (or the received vector v) in view of the generator matrix G4. The main loop of the process is executed as follows: <ul id="ul0012" list-style="dash" compact="compact"><li>Let p'=0, i'=0, and δ=(δ1, ..., δn) =(0, ..., 0)</li><li>For i=0, 8, 16, ..., to 120 <ul id="ul0013" list-style="dash" compact="compact"><li>Let αI= σI(γIi),..., αIV= σIV(YIVi)</li><li>Let p= <maths id="math0042" num=""><math display="inline"><mrow><mfenced open="|" close="|"><mrow><msub><mrow><mtext>α</mtext></mrow><mrow><mtext>I</mtext></mrow></msub></mrow></mfenced></mrow></math><img file="EP1237284A1_D0042.tif" /></maths> + ... + <maths id="math0043" num=""><math display="inline"><mrow><mfenced open="|" close="|"><mrow><msub><mrow><mtext>α</mtext></mrow><mrow><mtext>IV</mtext></mrow></msub></mrow></mfenced></mrow></math><img file="EP1237284A1_D0043.tif" /></maths></li><li>If odd number of negative αN's: <ul id="ul0014" list-style="dash" compact="compact"><li>switch sign of smallest magnitude αN</li><li>let p=p - 2 minN |αN|</li></ul></li><li>Compute βI=sign(αI), ..., βIV=sign(αIV)</li><li>If p>p', let p'=p, i'=i, and δ' = (βIβIβIβI, ..., βIVβIVβIVβIV, +1, +1, +1)</li></ul></li><li>The maximum likelihood codeword in antipodal form is then:<maths id="math0044" num=""><math display="block"><mrow><mover accent="true"><mrow><mtext>y</mtext></mrow><mo>¯</mo></mover><msub><mrow><mtext>* = (δ</mtext></mrow><mrow><mtext>1</mtext></mrow></msub><msubsup><mrow><mover accent="true"><mrow><mtext>y</mtext></mrow><mo>¯</mo></mover></mrow><mrow><mtext>i1</mtext></mrow><mrow><mtext>"</mtext></mrow></msubsup><msub><mrow><mtext>,···,δ</mtext></mrow><mrow><mtext>n</mtext></mrow></msub><msubsup><mrow><mover accent="true"><mrow><mtext>y</mtext></mrow><mo>¯</mo></mover></mrow><mrow><mtext>in</mtext></mrow><mrow><mtext>"</mtext></mrow></msubsup><mtext>),</mtext></mrow></math><img file="EP1237284A1_D0044.tif" /></maths> or in binary form:<maths id="math0045" num=""><math display="block"><mrow><mtext>y* = </mtext><mfrac><mrow><mtext>1</mtext></mrow><mrow><mtext>2</mtext></mrow></mfrac><mtext> - </mtext><mfrac><mrow><mtext>1</mtext></mrow><mrow><mtext>2</mtext></mrow></mfrac><mover accent="true"><mrow><mtext>y</mtext></mrow><mo>¯</mo></mover><mtext>*,</mtext></mrow></math><img file="EP1237284A1_D0045.tif" /></maths></li></ul> with the corresponding information bits denoted u*. In summary then, y* is the maximum likelihood estimate of the modified received codeword w. In essence, and as an alternative, the same processing algorithm as used for the (19,7) extended Golay code discussed above may again be used here by appending a zero to the received vector w.

0037As discussed previously, the conventional error correction decoder 40 computes the Hamming distance dH between the candidate vector (corresponding to the selected closest bit vector u) and the received vector v. This Hamming distance identifies the number of places where the bits of candidate vector and the received vector v differ, thus providing an error estimate for output along with the bit vector u. Use of the Hamming distance is not preferred, however, because the Hamming distance calculation tends to discard too much available and important information. It also does not exploit available channel tap estimate information. A Euclidean distance calculation rather than a Hamming distance calculation would provide better results.

0038Reference is now made to FIGURE 4 wherein there is shown a block diagram of a decoder 40 of the present invention implementing a Euclidean distance based error estimation determination. Let <maths id="math0046" num=""><math display="inline"><mrow><mover accent="true"><mrow><mtext mathvariant="bold">y</mtext></mrow><mo>¯</mo></mover></mrow></math><img file="EP1237284A1_D0046.tif" /></maths>* denote the selected codeword choice y* 110 in antipodal form. The error estimate for the decoding operation is determined by computing the Euclidean distance dE 114 between the received vector w and <maths id="math0047" num=""><math display="inline"><mrow><mover accent="true"><mrow><mtext mathvariant="bold">y</mtext></mrow><mo>¯</mo></mover></mrow></math><img file="EP1237284A1_D0047.tif" /></maths>* as follows:<maths id="math0048" num=""><img file="EP1237284A1_D0048.tif" /></maths> The error estimate e is then appropriately scaled and quantized 116 in accordance with the type of code at issue. For example, for the error control decoders 40 decoding the Hamming codes, e is scaled and quantized to be either zero or one. For the Golay codes, on the other hand, e is scaled and quantized to be either zero, one, two or three.

0039The deinterleaver unit 38, decoders 40 (including their functional component parts illustrated in FIGURES 3 and 4), and bit vector reconstruction unit 44 are all preferably implemented as a specialized digital signal processor (DSP) or in an application specific integrated circuit (ASIC). It will, of course, be understood that the deinterleaver unit 38, decoders 40 (including their functional component parts illustrated in FIGURES 3 and 4), and bit vector reconstruction unit 44 may alternatively be implemented using discrete components and perhaps distributed processing. In either case, the deinterleaver unit 38, decoders 40 (including their functional component parts illustrated in FIGURES 3 and 4), and bit vector reconstruction unit 44 each perform and implement the functional operations previously described.

0040Although preferred embodiments of the present invention have been illustrated in the accompanying Drawings and described in the foregoing Detailed Description, it will be understood that the invention is not limited to the embodiments disclosed, but is capable of numerous rearrangements., modifications and substitutions without departing from the spirit of the invention as set forth and defined by the following claims.

Contents4

Every citation, both ways

Citations
Document	Relation	Office	Category	Cited during	Relevant claims
US12462814B2	Cited by	United States of America	–	Applicant	–
US8433562B2	Cited by	United States of America	–	Applicant	–
EP1465158A3	Cited by	European Patent Office (EPO)	–	Search report	–
US11270714B2	Cited by	United States of America	–	Applicant	–
US12254895B2	Cited by	United States of America	–	Applicant	–
US8359197B2	Cited by	United States of America	–	Applicant	–
US12451151B2	Cited by	United States of America	–	Applicant	–
US8595002B2	Cited by	United States of America	–	Applicant	–
US11990144B2	Cited by	United States of America	–	Applicant	–
EP1465158A2	Cited by	European Patent Office (EPO)	–	Search report	–
US8036886B2	Cited by	United States of America	–	Applicant	–
US4933956A	Cites	United States of America	A	Search report	1-8
US5517511A	Cites	United States of America	A	Search report	1-8

17 members in 13 offices

This recordMember, by publication datePriority claim3 more offices are in the list below

Priority claims3

Priority claims
Document	Office	Kind	Date
768530	United States of America	–	1996-12-18
76853096	United States of America	A	1996-12-18
97952342	European Patent Office (EPO)	A	1997-12-15

Members17

Family members, oldest first
Document	Office	Kind
CA2275488A1	Canada	A1	1998-06-25
WO9827659A1	World Intellectual Property Organization (WIPO)	A1	1998-06-25
AU5597498A	Australia	A	1998-07-15
ID22139A	Indonesia	A	1999-09-09
EP0947052A1	European Patent Office (EPO)	A1	1999-10-06
US5968199A	United States of America	A	1999-10-19
EE9900253A	Estonia	A	1999-12-15
BR9713761A	Brazil	A	2000-02-01
CN1247648A	China	A	2000-03-15
KR20000069575A	Republic of Korea	A	2000-11-25
AU731218B2	Australia	B2	2001-03-29
JP2001506447A	Japan	A	2001-05-15
HK1026529A1	Hong Kong, China	A1	2001-08-31
EP1237284A1This record	European Patent Office (EPO)	A1	2002-09-04
CN1100392C	China	C	2003-01-29
EP0947052B1	European Patent Office (EPO)	B1	2003-03-26
DE69720260D1	Germany	D1	2003-04-30

9 legal events, as the office reported them to INPADOC

Over the term

Point at a mark for the event

Events

Legal events, newest first
	Event	Code
2005-04-13	Application deemed to be withdrawnWithdrawn18D	18D
2005-02-25	Information on the status of an ep patent application or granted ep patentGrantedSTATUS: THE APPLICATION IS DEEMED TO BE WITHDRAWNSTAA	STAA
2004-01-02	Party data changed (applicant data changed or rights of an application transferred)RAP1	RAP1
2003-07-16	First examination report despatched17Q	17Q
2003-05-21	Designation fees paidAKX	AKX
2002-09-04	Request for examination filed17P	17P
2002-09-04	Divisional application: reference to earlier applicationAC	AC
2002-09-04	Designated contracting statesAK	AK
2002-07-19	Public reference made under article 153(3) epc to a published international application that has entered the european phaseORIGINAL CODE: 0009012PUAI	PUAI