Factorial packing method and apparatus for information coding

Details Factorial packing method and apparatus for information coding Factorial packing method and apparatus for information coding

1999-08-06

2001-05-22

{haeck over (S)}mits, T{overscore (a)}livaldis I. (Department: 2641)

Data processing: speech signal processing, linguistics, language

Speech signal processing

For storage or transmission

C704S201000, C704S500000, C704S236000

Reexamination Certificate

active

06236960

ABSTRACT:

FIELD OF THE INVENTION
The present invention relates, in general, to communication systems and, more particularly, to coding information signals in such communication systems.
BACKGROUND OF THE INVENTION
Code-division multiple access (CDMA) communication systems are well known. One exemplary CDMA communication system is the so-called IS-95 which is defined for use in North America by the Telecommunications Industry Association (TIA). For more information on IS-95, see TIA/EIA/IS-95,
Mobile Station
-
Base
-
station Compatibility Standard for Dual Mode Wideband Spread Spectrum Cellular System,
January 1997, published by the Electronic Industries Association (EIA), 2001 Eye Street, N.W., Washington, D.C. 20006. A variable rate speech codec, and specifically Code Excited Linear Prediction (CELP) codec, for use in communication systems compatible with IS-95 is defined in the document known as IS-127 and titled
Enhanced Variable Rate Codec, Speech Service Option
3
for Wideband Spread Spectrum Digital Systems,
September 1996. IS-127 is also published by the Electronic Industries Association (EIA), 2001 Eye Street, N.W., Washington, D.C. 20006.
In the IS-127 Rate 1 case (8.5 kbps), the fixed codebook (FCB) uses a multipulse configuration (known as Algebraic Code Excited Linear Prediction or ACELP) in which the excitation vector c
k
contains only eight non-zero, unit magnitude values, or “pulses”. For the eight pulses, there are 35 bits allocated for the pulse positions and associated signs for each of the three subframes (of length L=[53, 53, 54]). An associated “track” defines the allowable positions for each of the eight pulses within c
k
as defined in IS-127. In this configuration, three of the tracks contain two pulses and two tracks contain only one pulse. As shown in Table 1 (from Table 4.5.7.1-1 of IS-127), the pulse(s) on track 0 can occupy positions 0, 5, 10, . . . , 50, pulse(s) on track 2 can occupy positions 1, 6, 11, . . . , 51, and so on. This is known as “interleaved pulse permutation.” The positions of the eight pulses are then chosen in a manner such that equation (12), recited below, is maximized in a reasonable number of iterations.
TABLE 1
IS-127 Rate 1 Pulse Positions Definitions
Track
Positions
T0
0, 5, 10, 15, 20, 25, 30, 35, 40, 45, 50
T1
1, 6, 11, 16, 21, 26, 31, 36, 41, 46, 51
T2
2, 7, 12, 17, 22, 27, 32, 37, 42, 47, 52
T3
3, 8, 13, 18, 23, 28, 33, 38, 43, 48, 53
T4
4, 9, 14, 19, 24, 29, 34, 39, 44, 49, 54
In an effort to improve upon the IS-127 codebook design for higher bit rates, a design requirement may be to have twelve total pulses with three pulses on each of four separate tracks, with subframe sizes of L=[53, 53, 54], and a bit allocation of 48 bits per subframe. The advantage of having multiple pulses on a given track is (at least) twofold. First, multiple pulse tracks tend to be longer because there are fewer of them. This promulgates greater flexibility in pulse positioning; i.e., shorter track lengths limit flexibility and can potentially force pulses into suboptimal positions, resulting in decreased performance. Secondly, multiple pulses can “degenerate” into fewer pulses, i.e., pulses can occupy the same positions and become additive. This tends to refine the shape of the excitation sequence and hence, be a closer match to the target signal by providing limited amplitude information, as a byproduct of positioning information. Here, some of the benefits of the traditional multipulse (amplitude and position) are preserved. For additional information, see the article by I. M. Transcoso and B. S. Atal titled “Efficient Procedures for Finding the Optimum Innovation in Stochastic Coders” in the
Proc. Int. Conf. Acoust., Speech, Signal Processing,
1987 at pages 1957-1960.
In the given scenario, the tracks would be configured as 4 tracks×14 positions=56 total positions, which could be positioned according to Table 2. Here, the bit allocation of 48 bits would be divided between the 4 tracks equally so that each track would receive 12 bits. The 12 bits per track would further be composed of 3 bits for each position and 1 sign bit to indicate the polarity of the each pulse. The problem is that only 8 positions can be represented by 3 bits (2
3
=8). Coding the positions using 4+1=5 bits per pulse would require 60 bits per subframe, so that it is obvious that the requirement cannot be met in such a straightforward manner.
TABLE 2
Required Pulse Position Definitions
Track
Positions
T0
0, 4, 8, 12, 16, 20, 24, 28, 32, 36, 40, 44, 48, 52
T1
1, 5, 9, 13, 17, 21, 25, 29, 33, 37, 41, 45, 49, 53
T2
2, 6, 10, 14, 18, 22, 26, 30, 34, 38, 42, 46, 50, 54
T3
3, 7, 11, 15, 19, 23, 27, 31, 35, 39, 43, 47, 51, 55
A method for pulse coding that is known in the prior art deals with multiplexing the indices of two pulses into a single codeword. For example, in the IS-127 Rate 1 case (8.5 kbps), there are 11 possible pulse positions spread over five tracks. Rather than using four bits for each pulse position, the positions of two pulses can be coded jointly using only seven bits. This is accomplished by considering that the total number of positions for two pulses is 11×11=121, which is less than the total number of positions that can be coded with seven bits (2
7
=128). Details of the coding can then be expressed as:
codeword
=
N
pos
·
⌊
p
i
N
track
⌋
+
⌊
p
j
N
track
⌋
where p
i
and p
j
are the positions of the i-th and j-th pulses, N
pos
is the number of pulse positions per track, N
track
is the number of tracks, and └x┘ represents the largest integer less than or equal to x. The pulse positions can then be extracted at the decoder by:
λ
i
=
⌊
codeword
N
pos
⌋
,
 
⁢
λ
j
=
codeword
-
N
pos
·
λ
i
,
where &lgr;
i
and &lgr;
j
are the decimated positions within the appropriate track, which corresponds to the columns in Table 2 (i.e., p
i
=N
t
&lgr;
i
+n where N
t
is the number of tracks, and n is the track number). The problem with using this method for the 14 position, 3 pulse track case in Table 2, is that a 14×14×14=2,744 position multiplex would still require 12 bits (2
12
=4096 possible positions), so there is no savings over simply using four bits for each pulse position.
In the case of multiple pulse tracks, however, there is a built-in redundancy that has been exploited in the prior art. Again in IS-127, the two pulse track positions are indistinct, i.e., the first pulse can be interchanged with the second pulse with no change in outcome. Therefore, efficient sign coding has been embedded in the position information: if the signs of the two pulses are the same, the packing order is such that the pulses are ascending in position (i.e., the position of the first pulse is less than or equal to the position of the second pulse, or p
i
≦p
j
). Otherwise, the positions are descending (the position of the first pulse is greater than the position of the second pulse, or p
i
>p
j
). This allows the tracks to be coded using only 7 bits plus 1 sign bit (instead of 2) for a total of 8 bits for an 11 position double pulse track.
In a triple pulse track, however, the complexity of this problem grows at a factorial rate. Rather than having 2!=2 permutations of indistinct pulses as described above, there are 3!=6 permutations, as shown in Table 3. In addition, there are 4 combinations of pulse degeneracy, in which two or more pulses occupy the same positions, also shown in Table 3.
TABLE 3
Redundancies in Triple Pulse Coding
Indistinct Pulse
Degenerative Pulse
Combinations
Combinations
p
i
≦ p
j
≦ p
k
p
i
= p
j
≠ p
k
p
i
≦ p
k
≦ p
j
p
i
≠ p
j
= p
k
p
j
≦ p
i
≦ p
k
p
i
= p
k
≠ p
j
p
k
≦ p
j
≦ p
i
p
i
= p
j
= p
k
p
j
≦ p
k
≦ p
i
p
k
≦ p
i
≦ p
j
One problem with the prior art in this case is that the

Affiliated with

Also associated with

Rating

Factorial packing method and apparatus for information coding does not yet have a rating. At this time, there are no reviews or comments for this patent.

If you have personal experience with Factorial packing method and apparatus for information coding, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Factorial packing method and apparatus for information coding will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFUS-PAI-O-2516058