Data processing: speech signal processing – linguistics – language – Speech signal processing – Recognition
Reexamination Certificate
2001-04-30
2004-03-16
Dorvil, Richemond (Department: 2654)
Data processing: speech signal processing, linguistics, language
Speech signal processing
Recognition
C704S256000, C382S115000, C382S186000
Reexamination Certificate
active
06708149
ABSTRACT:
FIELD OF THE INVENTION
The present invention relates generally to a method and apparatus for decoding received symbols. More particularly, the present invention discloses a vector fix-lag algorithm for determining the probabilities of transmitted symbols given received symbols.
BACKGROUND OF THE INVENTION
Forward-backward algorithms (FBAs) are often used in a variety of applications such as speech recognition, handwriting verification such as signature verification, error correction code decoding, etc., to calculate probabilities. As the name suggests, FBAs are a combination of forward algorithms and backward algorithms using vector-matrix products. Equipment that performs the algorithms requires large amounts of memory for storing all the matrices and intermediate matrix products needed to support the algorithms.
FBAs can be used to calculate the probabilities associated with the functions of Hidden Markov Models (HMMs) in voice recognition to recognize discrete and continuous speech. When a HMM is applied to describe a communication channel, products of sequences of probability density matrices are used to estimate the a posteriori probabilities of transmitted symbols given the received symbols. In other words, mathematical models are used to estimate the probabilities of the transmitted symbol knowing the received symbol.
Conventional FBA techniques require that a sequence of matrices multiplied by a first vector in a recursive manner in a forward part of the algorithm be stored in memory. The decoding process can start only after a long sequence of symbols has been received. This is unacceptable in many applications (a telephone application, for example) that impose strict constraints on the message delivery delay. Thus, new technology is needed to improve the vector-matrix product calculation that enables a decoder to estimate the product, and thus estimate the input symbols, without waiting for the whole symbol sequence to be received. This technology enables a designer to trade the product estimation accuracy for smaller delays in information delivery.
SUMMARY OF THE INVENTION
The invention provides a method and apparatus that performs a fixed-lag computation process.
The present invention discloses an apparatus and method of decoding information received over a noisy communications channel to determine the intended transmitted information. The present invention improves upon the traditional forward-backward algorithm with a vector fixed-lag algorithm. The algorithm is implemented by multiplying an initial state vector with a matrix containing information about the communications channel. The product is then recursively multiplied by the matrix &tgr; times, using the new product with each recursive multiplication. The new product forward information is stored in storage elements. The final product is multiplied with a final state column vector yielding a probability of a possible input. The estimated input is the input having the largest probability. The invention may be applied to a maximum a posteriori estimation of input symbols in systems modeled by an input-output HMM such as symbols transmitted over noisy channels, to handwriting and speech recognition and other probabilistic systems.
The vector fixed-lag process of the invention replaces the conventional forward-backward algorithm. This eliminates the need of saving long sequences of the forward vectors. Accordingly, memory requirements and decoding delay are reduced when using the fixed-lag process to decode information transmitted over a communication channel.
The present invention discloses a fixed-lag method for determining the probability of a transmitted symbol at a time t, transmitted along a communications channel with bursts of errors, given a received symbol. The method comprises obtaining initial state information vector about the channel and obtaining channel information matrices describing the probabilities that the transmitted symbol would be transmitted along a communications channel with and without error. The method further comprises generating intermediate probabilities, each intermediate probability being the product of the initial state information vector at a time previous to time t, and a channel information matrix, storing the intermediate probabilities in storage elements, and multiplying a last intermediate probability with a final state vector to yield the probability of the transmitted symbol.
REFERENCES:
patent: 5963906 (1999-10-01), Turin
patent: 6226613 (2001-05-01), Turin
William Turin, “MAP Decoding using the EM Algorithm,” Proc. IEEE 49th Vehicular Technology Conference, vol. 3, p. 1866-1870.*
William Turin and Michele Zorzi, “Performance Analysis of Delay-Constrained Communications over Diverse Burst-Error Channels,” Proc. IEEE 50th Vehicular Technology Conference, vol. 3, p. 1305-1309.*
William Turn, “MAP Decoding in Channels with Memory,” IEEE Trans. on Communications, vol. 48, No. 5, p. 757-763.*
William Turin, “The Forward-Backward Algorithm—Work Project No. 311614-2003”, Technical Memorandum, AT&T, Nov. 1997.
AT&T Corp.
Dorvil Richemond
Lerner Martin
LandOfFree
Vector fixed-lag algorithm for decoding input symbols does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Vector fixed-lag algorithm for decoding input symbols, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Vector fixed-lag algorithm for decoding input symbols will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3242431