Method and apparatus for generating a candidate code-vector to code an informational signal

A method (300) and apparatus (100) generate a candidate code-vector to code an information signal. The method can include producing (310) a target vector from a received input signal. The method can include constructing (320) a plurality of inverse weighting functions based on the target vector. The method can include evaluating (330) an error value associated with each of the plurality of inverse weighting functions to produce a fixed codebook code-vector. The method can include generating (340) a codeword representative of the fixed codebook code-vector, where the codeword can be used by a decoder to generate an approximation of the input signal.

BACKGROUND

The present disclosure relates, in general, to signal compression systems and, more particularly, to Code Excited Linear Prediction (CELP)-type speech coding systems.

Compression of digital speech and audio signals is well known. Compression is generally required to efficiently transmit signals over a communications channel or to compress the signals for storage on a digital media device, such as a solid-state memory device or computer hard disk. Although many compression techniques exist, one method that has remained very popular for digital speech coding is known as Code Excited Linear Prediction (CELP), which is one of a family of “analysis-by-synthesis” coding algorithms. Analysis-by-synthesis generally refers to a coding process by which multiple parameters of a digital model are used to synthesize a set of candidate signals that are compared to an input signal and analyzed for distortion. A set of parameters that yields a lowest distortion is then either transmitted or stored, and eventually used to reconstruct an estimate of the original input signal. CELP is a particular analysis-by-synthesis method that uses one or more codebooks where each codebook essentially includes sets of code-vectors that are retrieved from the codebook in response to a codebook index.

For example,FIG. 6is a block diagram of a CELP encoder600of the prior art. In CELP encoder600, an input signal s(n), such as a speech signal, is applied to a Linear Predictive Coding (LPC) analysis block601, where linear predictive coding is used to estimate a short-term spectral envelope. The resulting spectral parameters are denoted by the transfer function A(z). The spectral parameters are applied to an LPC Quantization block602that quantizes the spectral parameters to produce quantized spectral parameters Aqthat are suitable for use in a multiplexer608. The quantized spectral parameters Aqare then conveyed to multiplexer608, and the multiplexer608produces a coded bitstream based on the quantized spectral parameters and a set of codebook-related parameters, τ, β, k, and γ, that are determined by a squared error minimization/parameter quantization block607.

The quantized spectral, or Linear Predictive, parameters are also conveyed locally to an LPC synthesis filter605that has a corresponding transfer function 1/Aq(z). LPC synthesis filter605also receives a combined excitation signal u(n) from a first combiner610and produces an estimate of the input signal s(n) based on the quantized spectral parameters Aqand the combined excitation signal u(n). Combined excitation signal u(n) is produced as follows. An adaptive codebook code-vector cτis selected from an adaptive codebook (ACB)603based on an index parameter τ and the combined excitation signal from the previous subframe u(n-L). The adaptive codebook code-vector cτis then weighted based on a gain parameter β630and the weighted adaptive codebook code-vector is conveyed to first combiner610. A fixed codebook code-vector ckis selected from a fixed codebook (FCB)604based on an index parameter k. The fixed codebook code-vector ckis then weighted based on a gain parameter γ640and is also conveyed to first combiner610. First combiner610then produces combined excitation signal u(n) by combining the weighted version of adaptive codebook code-vector cτwith the weighted version of fixed codebook code-vector ck.

LPC synthesis filter605conveys the input signal estimate ŝ(n) to a second combiner612. The second combiner612also receives input signal s(n) and subtracts the estimate of the input signal ŝ(n) from the input signal s(n). The difference between input signal s(n) and the input signal estimate ŝ(n) is applied to a perceptual error weighting filter606, which filter produces a perceptually weighted error signal e(n) based on the difference between ŝ(n) and s(n) and a weighting function W(z). Perceptually weighted error signal e(n) is then conveyed to squared error minimization/parameter quantization block607. Squared error minimization/parameter quantization block607uses the error signal e(n) to determine an optimal set of codebook-related parameters τ, β, k, and γ that produce the best estimate ŝ(n) of the input signal s(n).

FIG. 7is a block diagram of a decoder700of the prior art that corresponds to the encoder600. As one of ordinary skilled in the art realizes, the coded bitstream produced by the encoder600is used by a demultiplexer708in the decoder700to decode the optimal set of codebook-related parameters, τ, β730, k, and γ740. The decoder700uses a process that is identical to the synthesis process performed by encoder600, by using an adaptive codebook703, a fixed codebook704, signals u(n) and u(n−L), code-vectors cτand ck, and a LPC synthesis filter705to generate output speech. Thus, if the coded bitstream produced by the encoder600is received by the decoder700without errors, the speech ŝ(n) output by the decoder700can be reconstructed as an exact duplicate of the input speech estimate s(n) produced by the encoder600.

While the CELP encoder600is conceptually useful, it is not a practical implementation of an encoder where it is desirable to keep computational complexity as low as possible. As a result,FIG. 8is a block diagram of an exemplary encoder800of the prior art that utilizes an equivalent, and yet more practical, system compared to the encoding system illustrated by encoder600. To better understand the relationship between the encoder600and the encoder800, it is beneficial to look at the mathematical derivation of encoder800from encoder600. For the convenience of the reader, the variables are given in terms of their z-transforms.

FromFIG. 6, it can be seen that the perceptual error weighting filter606produces the weighted error signal e(n) based on a difference between the input signal and the estimated input signal, that is:
E(z)=W(z)(S(z)−{circumflex over (S)}(z)).  (1)

From this expression, the weighting function W(z) can be distributed and the input signal estimate ŝ(n) can be decomposed into the filtered sum of the weighted codebook code-vectors:

The term W(z)S(z) corresponds to a weighted version of the input signal. By letting the weighted input signal W(z)S(z) be defined as Sw(z)=W(z)S(z) and by further letting the weighted synthesis filter605of the encoder600now be defined by a transfer function H(z)=W(z)/Aq(z), Equation 2 can rewritten as follows:
E(z)=Sw(z)−H(z)(βCτ(z)+γCk(z)).  (3)

By using z-transform notation, filter states need not be explicitly defined. Now proceeding using vector notation, where the vector length L is a length of a current speech input subframe, Equation 3 can be rewritten as follows by using the superposition principle:
e=sw−H(βcτ+γck)−hzir,  (4)

where:H is the L×L zero-state weighted synthesis convolution matrix formed from an impulse response of a weighted synthesis filter h(n), such as synthesis filters815and805, and corresponding to a transfer function Hzs(z) or H(z), which matrix can be represented as:

H=[h⁡(0)0⋯0h⁡(1)h⁡(0)⋯0⋮⋮⋱⋮h⁡(L-1)h⁡(L-2)⋯h⁡(0)],(5)hziris a L×1 zero-input response of H(z) that is due to a state from a previous speech input subframe,swis the L×1 perceptually weighted input signal,β is the scalar adaptive codebook (ACB) gain,cτis the L×1 ACB code-vector indicated by index τ,γ is the scalar fixed codebook (FCB) gain, andckis the L×1 FCB code-vector indicated by index k.

By distributing H, and letting the input target vector xw=sw−hzir, the following expression can be obtained:
e=xw−βHcτ−γHck.  (6)

Equation 6 represents the perceptually weighted error (or distortion) vector e(n) produced by a third combiner808of encoder800and coupled by the combiner808to a squared error minimization/parameter quantization block807.

From the expression above, a formula can be derived for minimization of a weighted version of the perceptually weighted error, that is, ∥e∥2, by squared error minimization/parameter quantization block807. A norm of the squared error is given as:
ε=∥e∥2=∥xw−βHcτ−γHck∥2.  (7)
Note that ∥e∥2may also be written as ∥e∥2=Σn=0L-1e2(n) or ∥e∥2=eTe, where eTis the vector transpose of e, and is presumed to be a column vector.

Due to complexity limitations, practical implementations of speech coding systems typically minimize the squared error in a sequential fashion. That is, the adaptive codebook (ACB) component is optimized first by assuming the fixed codebook (FCB) contribution is zero, and then the FCB component is optimized using the given (previously optimized) ACB component. The ACB/FCB gains, that is, codebook-related parameters β and γ, may or may not be re-optimized, that is, quantized, given the sequentially selected ACB/FCB code-vectors cτand ck.

The theory for performing such an example of a sequential optimization process is as follows. First, the norm of the squared error as provided in Equation 7 is modified by setting γ=0, and then expanded to produce:
ε=∥xw−βHcτ∥2=xwTxw−2βxwTHcτ+β2cτTHTHcτ.  (8)

Minimization of the squared error is then determined by taking the partial derivative of ε with respect to β and setting the quantity to zero:

This yields an optimal ACB gain:

Substituting the optimal ACB gain back into Equation 8 gives:

τ*=arg⁢⁢minτ⁢{xwT⁢xw-(xwT⁢Hcτ)2cτT⁢HT⁢Hcτ},(11)
where τ* is an optimal ACB index parameter, that is, an ACB index parameter that minimizes the bracketed expression. Typically, τ is a parameter related to a range of expected values of the pitch lag (or fundamental frequency) of the input signal, and is constrained to a limited set of values that can be represented by a relatively small number of bits. Since xwis not dependent on τ, Equation 11 can be rewritten as follows:

Now, by letting yτequal the ACB code-vector cτfiltered by weighted synthesis filter815, that is, yτ=Hcτ, Equation 13 can be simplified to:

τ*=arg⁢⁢maxτ⁢{(xwT⁢yτ)2yτT⁢yτ},(13)
and likewise, Equation 10 can be simplified to:

Thus Equations 13 and 14 represent the two expressions necessary to determine the optimal ACB index τ and ACB gain β in a sequential manner. These expressions can now be used to determine the optimal FCB index and gain expressions. First, fromFIG. 8, it can be seen that a second combiner806produces a vector x2, where x2=xw−βHcτ. The vector xw(or xw(n)) is produced by a first combiner804that subtracts a filtered past synthetic excitation signal hzir(n), after filtering past synthetic excitation signal u(n-L) by a weighted synthesis zero input response Hzir(z) filter801, from an output sw(n) of a perceptual error weighting filter W(z)802of input speech signal s(n). The term βHcτis a filtered and weighted version of ACB code-vector eτ, that is, ACB code-vector cτfiltered by zero state weighted synthesis filter Hzs(z)815to generate y(n) and then weighted based on ACB gain parameter β830. Substituting the expression x2=xw−βHcτinto Equation 7 yields:
ε=∥x2−γHck∥2.  (15)
where γHckis a filtered and weighted version of FCB code-vector ck, that is, FCB code-vector ckfiltered by zero state weighted synthesis filter Hzs(z)805and then weighted based on FCB gain parameter γ840. Similar to the above derivation of the optimal ACB index parameter τ*, it is apparent that:

k*=arg⁢⁢maxk⁢{(d2T⁢ck)2ckT⁢Φ⁢⁢ck},(17)
in which the optimal FCB gain γ is given as:

The encoder800provides a method and apparatus for determining the optimal excitation vector-related parameters τ, β, k, and γ. Unfortunately, higher bit rate CELP coding typically requires higher computational complexity due to a larger number of codebook entries that require error evaluation in the closed loop processing. Thus, there is an opportunity for generating a candidate code-vector to reduce the computational complexity to code an information signal.

DETAILED DESCRIPTION

As discussed above, higher bit rate CELP coding typically requires higher computational complexity due to a larger number of codebook entries that require error evaluation in the closed loop processing. Embodiments of the present disclosure can solve a problem of searching higher bit rate codebooks by providing for pre-quantizer candidate generation in a Code Excited Linear Prediction (CELP) speech coder. Embodiments can address the problem by generating a plurality of initial FCB candidates through direct quantization of a set of vectors formed using inverse weighting functions and the FCB target signal and then evaluating a weighted error of those initial candidates to produce a better overall code-vector. Embodiments can also apply variable weights to vectors and can sum the weighted vectors as part of preselecting candidate code-vectors. Embodiments can additionally generate a plurality of initial fixed codebook candidates through direct quantization of a set of vectors formed using inverse weighting functions and the fixed codebook target signal, and can then evaluate the weighted error of those initial candidates to produce a better overall code-vector. Other embodiments can also generate a plurality of initial FCB candidates through direct quantization of a set of vectors formed using inverse weighting functions and the FCB target signal, and then evaluating a weighted error of those initial candidates to determine a better initial weighting function for a given pre-quantizer function.

To achieve the above benefits, a method and apparatus can generate a candidate code-vector to code an information signal. The method can include receiving an input signal. The method can include producing a target vector from the input signal. The method can include constructing a plurality of inverse weighting functions based on the target vector. The method can include evaluating an error value associated with each of the plurality of inverse weighting functions to produce a Fixed Codebook (FCB) code-vector. The method can include generating a codeword representative of the FCB code-vector, where the codeword can be used by a decoder to generate an approximation of the input signal.

FIG. 1is an example block diagram of at least a portion of a coder100, such as a portion of the coder600, according to one embodiment. The coder100can include an input122, a target vector generator124, a FCB candidate code-vector generator110, a FCB104, a zero state weighted synthesis filter H105, an error minimization block107, a first gain parameter γ weighting block141, a combiner108, and an output126. The coder100can also include a second zero state weighted synthesis filter H115, a second error minimization block117, a second gain parameter γ weighting block142, and a second combiner118.

The zero state weighted synthesis filter105, the error minimization block107, and the combiner108, as well as the second zero state weighted synthesis filter H115, the second error minimization block117, and the second combiner118can operate similarly to the zero state weighted synthesis filter805, the squared error minimization parameter quantizer807, and the combiner808, respectively, as illustrated inFIG. 8. A codebook, such as the FCB104, can include of a set of pulse amplitude and position combinations. Each pulse amplitude and position combination can define L different positions and can include both zero-amplitude pulses and non-zero-amplitude pulses assigned to respective positions p=1, 2, . . . L of the combination.

In operation, the input122can receive and may process an input signal s(n). The input signal s(n) can be a digital or analog input signal. The input can be received wirelessly, through a hard-wired connection, from a storage medium, from a microphone, or otherwise received. For example, the input signal s(n) can be based on an audible signal, such as speech. The target vector generator124can receive the input signal s(n) from the input122and can produce a target vector x2from the input signal s(n).

The FCB candidate code-vector generator110can receive the target vector x2and can construct a plurality of candidate code-vectors ck[i]and an inverse weighting function ƒ(x2,i), where i can be an index for the candidate code-vectors ck[i]where 0≦i<N, and N is at least 2. The plurality of candidate code-vectors ck[i]can be based on the target vector x2and can be based on the inverse weighting function. The inverse weighting function can remove weighting from the target vector x2in some manner. For example, an inverse weighting function can be based on

f⁡(x2,i)=ai⁢rr+bi⁢d2d2,
described below, or can be other inverse weighting functions described below. Additionally, the FCB104may also use the inverse weighting function result as a means of further reducing the search complexity, for example, by searching only a subset of the total pulse/position combinations. The error minimization block117may also select one of a plurality of candidate code-vectors ck[i]with lower squared sum value of eias cki*. That is, after the best candidate code-vector cki* is found by way of square error minimization, the fixed codebook104may use cki* as an initial “seed” code-vector which may be iterated upon. The inverse weighting function result ƒ(x2, i*) may also be used in this process to help reduce search complexity. Thus, i* can represent the index value of the optimum candidate codevector ck[i]. If the coder100does not include the second zero state weighted synthesis filter H115, the second error minimization block117, the second gain parameter γ weighting block142, and the second combiner118, the remaining blocks can perform the corresponding functions. For example, the error minimization block107can provide the index i of the candidate codevectors and the index value i* of the optimum candidate codevector and the zero state weighted synthesis filter105can receive the candidate code-vectors ck[i](not shown).

According to an example embodiment, the FCB candidate code-vector generator110can construct the plurality of candidate code-vectors ck[i]based on the target vector x2, based on an inverse filtered vector, and based on a backward filtered vector as described below. The plurality of candidate code-vectors ck[i]can also be based on the target vector x2and based on a sum of a weighted inverse filtered vector and weighted backward filtered vector as described below.

The error minimization block117can evaluate an error vector eiassociated with each of the plurality of candidate code-vectors ck[i]. The error vector can be analyzed to select a single FCB code-vector ck[i*], where the FCB code-vector ck[i*]can be one of the candidate code-vectors ck[i]. The squared error minimization/parameter quantization block107can generate a codeword k representative of the FCB code-vector ck[i]. The codeword k can be used by a decoder to generate an approximation of the input signal s(n). The error minimization block107or another element can output the codeword k at the output126by transmitting the codeword k and/or storing the codeword k. For example, the error minimization block117may generate and output the codeword k.

Each candidate code-vector ck[i]can be processed as if it were generated by the FCB104by filtering it through the zero state weighted synthesis filter105for each candidate ck[i]. The FCB candidate code-vector generator110can evaluate an error value associated with each iteration of the plurality of candidate code-vectors ck[i]from the plurality of times to produce a FCB code-vector ckbased on the candidate code-vector ck[i]with the lowest error value.

The codeword k can also be generated without iterating it through more than one stage. For example, the codeword k can be generated without modification using blocks104,105, and108. For example, when FCB candidate code-vector generator110produces a sufficient number of pulses, it may already be a good approximation of the target signal x2without the need for a second stage. It can converge to the best value when it has sufficient bits. Thus, the ckcoming out of the fixed codebook104can be identical to the one of the vectors in the initial fixed codebook candidate code-vectors ck[i]. Furthermore, the FCB104may not even exist, such as in high bit rate applications where ck[i]may be good enough. In either case, the candidate code-vector ck[i]is equivalent to the final code-vector ck, and the index k may be subsequently transmitted or stored for later use by a decoder.

According to some embodiments, there can be multiple inverse functions f(x2,i), where 1<=i<=N and N>1, evaluated for every frame of speech. Multiple f(x2,i) outputs can be used to determine a codebook output, which can be ck[i]or ck. Additionally, ck[i]can be a starting point for determining ck, where ck[i]can allow for fewer iterations of k and can allow for a better overall result by avoiding local minima.

FIG. 2is an example block diagram of the FCB candidate code-vector generator110according to one embodiment. The FCB candidate code-vector generator110can include an inverse filter210, a backward filter220, and another processing block for a FCB candidate code-vector generator230.

The FCB candidate code-vector generator110can construct a plurality of candidate code-vectors ck[i], where i can be an index for the candidate code-vectors ck[i]. The plurality of candidate code-vectors ck[i]can be based on the target vector x2and can be based on an inverse weighting function, such as ƒ(x2,i). The inverse weighting function can be based on an inverse filtered vector and the inverse filter210can construct the inverse filtered vector from the target vector x2. For example, the inverse filtered vector can be constructed based on r=H−1x2, where r can be the inverse filtered vector, where H−1can be a zero-state weighted synthesis convolution matrix formed from an impulse response of a weighted synthesis filter, and where x2can be the target vector. Other variations are described in other embodiments.

The inverse weighting function can be based on a backward filtered vector, and the backward filter220can construct the backward filtered vector from the target vector x2. For example, the backward filtered vector can be constructed based on d2=HTx2, where d2can be the backward filtered vector, where HTcan be a transpose of a zero-state weighted synthesis convolution matrix formed from an impulse response of a weighted synthesis filter, and where x2can be the target vector. Other variations are described in other embodiments.

According to an example embodiment, recalling from the Background that
ε=∥x2−γHck∥2,  (15)(19)
if the FCB code-vector is given as:

ck=1γ⁢H-1⁢x2,(20)
then the error ε can tend to zero and the input signal s(n) and a corresponding coded output signal ŝ(n) can be identical. Since this is not practical for low rate speech coding systems, only a crude approximation of Eq. 20 is typically generated. U.S. Pat. No. 5,754,976 to Adoul, hereby incorporated by reference, discloses one example of the usage of the inverse filtered target signal r=H−1x2as a method for low bit rate pre-selection of the pulse amplitudes of the code-vector ck.

One of the problems in evaluating the error term ε in Eq. 19 is that, while the error ε is evaluated in the weighted synthesis domain, the FCB code-vector ckis generated in the residual domain. Thus, a direct PCM-like quantization of the right hand term in Eq. 20 does not generally produce the minimum possible error in Eq. 19, due to the quantization error generation being in the residual domain as opposed to the weighted synthesis domain. More specifically, the expression:

ck=QP⁢{1γ⁢H-1⁢x2},(21)
where QP{ } is a P-bit quantization operator, does not generally lead to the global minimum weighted error since the error due to QP{ } is a residual domain error. In order to achieve the lowest possible error in the weighted domain, many iterations of ckmay be necessary to minimize the error ε of Eq. 19. Various embodiments of the present disclosure described below can address this problem by reducing the iterations and by reducing the residual domain error.

First, an i-th pre-quantizer candidate ck[i]can be generated by the FCB candidate code-vector generator110using the expression
ck[i]=QP{ƒ(x2,i)}, 0≦i<N,(22)
where ƒ(x2,i) can be some function of the target vector, and N can be the number of pre-quantizer candidates. This expression can be a generalized form for generating a plurality of pre-quantizer candidates that can be assessed for error in the weighted domain. An example of such a function is given as:

where r=H1x2is the inverse filtered target signal, d2=HTx2is the backward filtered target as calculated/defined in Eq. 17, and aiand biare a set of respective weighting coefficients for iteration i. Here, |r| can be a norm of the residual domain vector r, such as the inverse filtered target vector r, given by ∥r∥=√{square root over (rTr)}, and likewise ∥d2∥=√{square root over (d2Td2)}. The effect of coefficients aiand bi, can be to produce a weighted sum of the inverse and backward filtered target vectors, which can then form the set of pre-quantizer candidate vectors.

Embodiments of the present disclosure can allow various coefficient functions to be incorporated into the weighting of the normalized vectors in Eq. 23. For example, the functions:
ai=1−i/(N−1),
bi=i/(N−1), 0≦i<N,(24)
where N is the total number of pre-quantizer candidates, can have a linear distribution of values. As an example, if N=4, the sets of coefficients can be: aiε{1.0, 0.667, 0.333, 0.0}, and biε{0.0, 0.333, 0.667, 1.0}. Another example may incorporate the results of a training algorithm, such as the Linde-Buzo-Gray (or LBG) algorithm, where many values of a and b can be evaluated offline using a training database, and then choosing aiand bibased on the statistical distributions. Such methods for training are well known in the art. Other functions can also be possible. For example, the following function may be found to be beneficial for certain classes of signals:
ƒ(x2,i)=air+birlpf,  (25)
where rlpfcan be a low pass filtered version of r. Alternatively, the LPF characteristic may be altered as a function of i:
ƒ(x2,i)=Bir,(26)
where Bimay be a class of linear phase filtering characteristics intended to shape the residual domain quantization error in a way that more closely resembles that of the error in the weighted domain. Yet another method may involve specifying a family of inverse perceptual weighting functions that may also shape the error in a way that is beneficial in shaping the residual domain error:
ƒ(x2,i)=Hi−1x2,  (27)

The weighted signal can then be quantified into a form that can be utilized by the particular FCB coding process. U.S. Pat. No. 5,754,976 to Adoul and U.S. Pat. No. 6,236,960 to Peng, hereby incorporated by reference, disclose coding methods that use unit magnitude pulse codebooks that are algebraic in nature. That is, the codebooks are generated on the fly, as opposed to being stored in memory, searching various pulse position and amplitude combinations, finding a low error pulse combination, and then coding the positions and amplitudes using combinatorial techniques to form a codeword k that is subsequently used by a decoder to regenerate ckand further generate an approximation of the input signal s(n).

According to one embodiment, the codebook disclosed in U.S. Pat. No. 6,236,960 can be used to quantify the weighted signal into a form that can be utilized by the particular FCB coding process. The i-th pre-quantizer candidate ck[i]may be obtained from Eq. 22 by iteratively adjusting a gain term gQas:

ck[i]=round⁡(gQ⁢f⁡(x2,i))⁢:⁢∑n⁢ck[i]⁡(n)=M,(28)
where the round( ) operator rounds the respective vector elements of gQƒ(x2,i) to the nearest integer value, where n represents the n-th element of vector ck[i], and M is the total number of unit magnitude pulses. This expression describes a process of selecting gQsuch that the total number of unit amplitude pulses in ck[i]equals M.

Many other ways of determining ck[i]from ƒ(x2,i) exist. For example, a median search based quantization method may be employed. This can be an iterative process involving finding an optimum pulse configuration satisfying the pulse sum constraint for a given gain and then finding an optimum gain for the optimum pulse configuration. A practical example of such a median search based quantization is given in ITU-T Recommendation G.718 entitled “Frame error robust narrow-band and wideband embedded variable bit-rate coding of speech and audio from 8-32 kbit/s”, section 6.11.6.2.4, pp. 153, which is hereby incorporated by reference.

The N different pre-quantizer candidates may then be evaluated according to the following expression (which is based on Eq. 17):

i*=arg⁢⁢max0≤i<N⁢{(d2T⁢ck[i])2ck[i]⁢T⁢Φ⁢⁢ck[i]},(29)
where ck[i]can be substituted for ck, and the best candidate i* out of N candidates can be selected. Alternatively, i* may be determined through brute force computation:

i*=arg⁢⁢max0≤i<N⁢{(x2T⁢y2[i])2y2[i]T⁢y2[i]},(30)
where y2[i]=Hck[i]and can be the i-th pre-quantizer candidate filtered though the zero state weighted synthesis filter105. The latter method may be used for complexity reasons, especially when the number of non-zero positions in the pre-quantizer candidate, ck[i], is relatively high or when the different pre-quantizer candidates have very different pulse locations. In those cases, the efficient search techniques described in the prior art do not necessarily hold.

After the best pre-quantizer candidate ck[i*]is selected, a post-search may be conducted to refine the pulse positions, and/or the signs, so that the overall weighted error is reduced further. The post-search may be one described by Eq. 29. In this case, the numerator and denominator of Eq. 29 may be initialized by letting ck=ck[i*], and then iterating on k to reduce the weighted error. It is not necessary for ck[i*]to contain the exact number of pulses as allowed by the FCB. For example, the FCB configuration may allow ckto contain 20 pulses, but the pre-quantizer stage may use only 10 or 15 pulses. The remaining pulses can be placed by the post search. In another case, the pre-quantizer stage may place more pulses than allowed by the FCB configuration. In this embodiment, the post search may remove pulses in a way that attempts to minimize the weighted error. In yet another embodiment, the number of pulses can be high enough where a post search is not needed since the pre-quantizer candidates can provide adequate quality for a particular application. In one embodiment, however, the number of pulses in the pre-quantizer vector can be generally equal to the number of pulses allowed by a particular FCB configuration. In this case, the post search may involve removing a unit magnitude pulse from one position and placing the pulse at a different location that results in a lower weighted error. This process may be repeated until the codebook converges or until a predetermined maximum number of iterations is reached.

To further expand on the above embodiments where the candidate code-vectors ck[i]and the eventual FCB output vector ckmay or may not contain the same number of unit magnitude pulses, another embodiment exists where the candidate codebook for generating ck[i]may be different than the codebook for generating ck. That is, the best candidate ck[i*]may generally be used to reduce complexity or improve overall performance of the resulting code-vector ck, by using ck[i*]as a means for determining the best inverse function ƒ(x2,i*), and then proceeding to use ƒ(x2,i*) as a means for searching a second codebook c′k. Such an example may include using a Factorial Pulse Coded (FPC) codebook for generating ck[i*], and then using a traditional ACELP codebook to generate c′k, wherein the inverse function ƒ(x2,i*) is used in the secondary codebook search c′k, and the candidate code-vectors ck[i]are discarded. In this way, for example, the pre-selection of pulse signs for the secondary codebook c′kmay be based on a plurality of inverse functions ƒ(x2,i), and not directly on the candidate code-vectors ck[i]. This embodiment may allow performance improvement to existing codecs that use a specific codebook design, while maintaining interoperability and backward compatibility.

In another embodiment, a very large value of N may be used. For example, if N=100, then the weighting coefficients [ai, bi] can span a very high resolution set, and can result in a solution that will yield optimal results.

According to U.S. Pat. No. 7,054,807 to Mittal, which is hereby incorporated by reference, the ACB/FCB parameters may be jointly optimized. The joint optimization can also be used for evaluation of N pre-quantizer candidates. Now Eq. 29 can become:

i*=arg⁢⁢max0≤i<N⁢{(d2T⁢ck[i])2ck[i]⁢T⁢Φ′⁢ck[i]},(31)
where Φ′=Φ−yyTand where y can be a scaled backward filtered ACB excitation. Now i* may be determined through brute force computation:

i*=arg⁢⁢max0≤i<N⁢{(x2T⁢y2[i])2y2[i]T⁢y2[i]-(yT⁢ck[i])2},(32)
where y2[i]=Hck[i]can be the i-th pre-quantizer candidate filtered though the zero state weighted synthesis filter105and yTck[i]can be a correlation between the i-th pre-quantizer candidate and the scaled backward filtered ACB excitation.

FIG. 3is an example illustration of a flowchart300outlining the operation of the coder100according to one embodiment. The flowchart300illustrates a method that can include the embodiments disclosed above.

At310, a target vector x2can be generated from a received input signal s(n). The input signal s(n) can be based on an audible speech input signal. At320, a plurality of inverse weighting functions ƒ(x2,i) can be constructed based on the target vector x2. Optionally, a plurality of candidate code-vectors ck[i]can also be constructed based on the target vector x2and based on an inverse weighting function ƒ(x2,i). The plurality of inverse weighting functions ƒ(x2,i) (and/or plurality of candidate code-vectors ck[i]) can be constructed based on an inverse filtered vector and based on a backward filtered vector along with the target vector x2. The plurality of inverse weighting functions ƒ(x2,i) (and/or plurality of candidate code-vectors ck[i]) can also be constructed based on a sum of a weighted inverse filtered vector and a weighted backward filtered vector along with the target vector x2.

At330, an error value ε associated with each code-vector of the plurality of inverse weighting functions ƒ(x2,i) (and/or plurality of candidate code-vectors ck[i]) can be evaluated to produce a fixed codebook code-vector ck. For example, errors ε[i] of ck[i]can be evaluated to produce ck[i*], then ck[i*]can be used as a basis for further searching on ck. The value k can be the ultimate codebook index that is output.

At340, a codeword k representative of the fixed codebook code-vector ckcan be generated, where the codeword can be used by a decoder to generate an approximation of the input signal s(n). At350, the codeword k can be output. For example, the codeword k can be a fixed codebook index parameter codeword k that can be output by transmitting the fixed codebook index parameter k and/or storing the fixed codebook index parameter k.

FIG. 4is an example illustration of a flowchart400outlining the operation of block320ofFIG. 3according to one embodiment. At410, an inverse filtered vector r can be constructed from the target vector x2. The inverse weighting function ƒ(x2, i) of block320can be based on the inverse filtered vector r constructed from the target vector x2. The inverse filtered vector r can be constructed based on r=H−1x2, where r can be the inverse filtered vector, where H−1can be a zero-state weighted synthesis convolution matrix formed from an impulse response of a weighted synthesis filter, and where x2can be the target vector. Other variations are described in other embodiments above.

At420, a backward filtered vector d2can be constructed from the target vector x2. The inverse weighting function ƒ(x2, i) of block320can be based on the backward filtered vector d2constructed from the target vector x2. The backward filtered vector d2can be constructed based on d2=HTx2, where d2can be the backward filtered vector, where HTcan be a transpose of a zero-state weighted synthesis convolution matrix formed from an impulse response of a weighted synthesis filter, and where x2can be the target vector. Other variations are described in other embodiments above.

At430, a plurality of inverse weighting functions ƒ(x2,i) (and/or plurality of candidate code-vectors ck[i]) can be constructed based on a weighting of the inverse filtered vector r and a weighting of the backward filtered vector d2, where the weighting can be different for each of the associated candidate code-vectors ck[i]. For example, the weighting can be based on

f⁡(x2,i)=ai⁢rr+bi⁢d2d2
or other weighting described above.

FIG. 5is an example illustration500of two conceptual candidate code-vectors ck[i]for i=1 and i=2 according to one embodiment. The candidate code-vectors ck[i]and ck[2]can correspond to factorial pulse coded vectors for different functions ƒ(x2, 1) and ƒ(x2, 2) of a target vector. As discussed above, one of the candidate code-vectors, ck[i], can be used as a basis for choosing codeword ckthat generates a fixed codebook index parameter k. The fixed codebook index parameter k can identify, at least in part, a set of pulse amplitude and position combinations, such as including a pulse amplitude510and a position520, in a codebook. Each pulse amplitude and position combination can define L different positions and can include both zero-amplitude pulses and non-zero-amplitude pulses assigned to respective positions p=1, 2, . . . L of the combination. The set of pulse amplitude and position combinations can be used for functions ƒ(x2, 1) and ƒ(x2, 2) for a chosen candidate code-vector ck[i*], such as, for example, code-vector ck[1]. The illustration500is only intended as a conceptual example and does not correspond to any actual number of pulses, positions of pulses, code-vectors, or signals.

In this document, relational terms such as “first,” “second,” and the like may be used solely to distinguish one entity or action from another entity or action without necessarily requiring or implying any actual such relationship or order between such entities or actions. The term “coupled,” unless otherwise modified, implies that elements may be connected together, but does not require a direct connection. For example, elements may be connected through one or more intervening elements. Furthermore, two elements may be coupled by using physical connections between the elements, by using electrical signals between the elements, by using radio frequency signals between the elements, by using optical signals between the elements, by providing functional interaction between the elements, or by otherwise relating two elements together. Also, relational terms, such as “top,” “bottom,” “front,” “back,” “horizontal,” “vertical,” and the like may be used solely to distinguish a spatial orientation of elements relative to each other and without necessarily implying a spatial orientation relative to any other physical coordinate system. The terms “comprises,” “comprising,” or any other variation thereof, are intended to cover a non-exclusive inclusion, such that a process, method, article, or apparatus that comprises a list of elements does not include only those elements but may include other elements not expressly listed or inherent to such process, method, article, or apparatus. An element proceeded by “a,” “an,” or the like does not, without more constraints, preclude the existence of additional identical elements in the process, method, article, or apparatus that comprises the element. Also, the term “another” is defined as at least a second or more. The terms “including,” “having,” and the like, as used herein, are defined as “comprising.”