Back to results
US 7,461,106 B2Granted
Apparatus and method for low complexity combinatorial coding of signals
AssigneeMotorola, Inc.
InventorsUdar Mittal, James P. Ashley, Edgardo M. Cruz-Zeno
Life of this patent
Estimating the term…
Abstract
The invention utilizes low complexity estimates of complex functions to perform combinatorial coding of signal vectors. The invention disregards the accuracy of such functions as long as certain sufficient properties are maintained. The invention in turn may reduce computational complexity of certain coding and decoding operations by two orders of magnitude or more for a given signal vector input.
Claims9
A method for combinatorial coding and decoding within circuitry, the method comprising the steps of:
- receiving within the circuitry a signal vector comprising speech, audio, image, or video signal;
- receiving within the circuitry a value n based on a number of positions in the signal vector;
- receiving within the circuitry a value d based on a number of occupied positions within the signal vector;
- generating within the circuitry F′(n, d) based on n and d, wherein F′(n, d) is related to F(n, d) such that F′(n, d)>F(n, d) and F′(n, d)>F′(n−1, ,d)+F′(n−1, d−1), and wherein
- F
-
- (
- n
- ,
- d
- )
- =
- n
- !
- d
- !
-
- (
- n
- -
- d
- )
- !
- ;
- and
- wherein the step of generating F′(n, d) comprises the step of generating
- F
- ′
-
- (
- n
- ,
- d
- )
- =
- R
- ′
-
- (
- ∑
- i
- =
- n
- -
- d
- +
- 1
- n
-
- P
- ′
-
- (
- i
- )
- -
- Q
- ′
-
- (
- d
- )
- )
- ,
- where P′(i), Q′(d), and R′(k), are approximations of the functions P(i)=loga(i),
- Q
-
- (
- d
- )
- =
- ∑
- j
- =
- 1
- d
-
- log
- a
-
- (
- j
- )
- ,
- and
-
-
- R
-
- (
- k
- )
- =
- a
- k
- ,
- respectively, where a is an arbitrary logarithmic base;
- using within the circuitry F′(n, d) to code or decode the signal vector to produce coded or decoded speech, audio, image, or video;
- and
- outputting from the circuitry the coded or decoded speech, audio, image, or video signals.
97 more elements
An apparatus comprising:
- vector generator circuitry receiving a signal vector comprising speech, audio, image, or video and outputting vector Xcc;
- combinatorial function generator circuitry generating function F′(n, r) having properties F′(n,r)>F(n,r) and F′(n,r)>F′(n−1, r)+F′(n−1, r−1) where F′(n,r) is used encode/decode the vector Xcc and wherein function F′(n,r) is given as:
- F
- ′
-
- (
- n
- ,
- r
- )
- =
- R
- ′
-
- (
- ∑
- i
- =
- n
- -
- r
- +
- 1
- n
-
- P
- ′
-
- (
- i
- )
- -
- Q
- ′
-
- (
- r
- )
- )
- ,
- where P′(i) and Q′(r) are given as:
- P
- ′
-
- (
- i
- )
- =
- 2
- -
- 21
-
- ⌊
- 2
- 21
-
- log
- 2
-
- (
- i
- )
- +
- 1
- ⌋
- ,
- i
- ∈
- [
- 1
- ,
- 2
- ,
- …
-
- ,
- 144
- ]
- and
- Q
- ′
-
- (
- r
- )
- =
- {
-
- 0
- ,
-
- r
- =
- 1
- ∑
- j
- =
- 2
- r
-
- 2
- -
- 14
-
- ⌊
- 2
- 14
-
- log
- 2
-
- (
- j
- )
- -
- 1
- ⌋
- ,
-
- r
- ∈
- [
- 2
- ,
- …
-
- ,
- 28
- ]
- ,
- and where R′(k) is an approximation of function R′(k)≈2k, given as:
- R′(k)=└2kt−19└219Kf┘┘,
- where k=ki+kf is broken down into integer and fractional components of k, and Kf=2kf is a Taylor series expansion of a fractional component of k;
- and
- a coder circuitry receiving F′(n,r) and the signal vector and outputting coded speech, audio, image, or video signals based on the vector Xcc and F′(n,r).
132 more elements
An apparatus comprising:
- combinatorial function generator circuitry outputting function F′(n, r) having the properties F′(n,r)>F(n,r) and F′(n,r)>F′(n−1, r)+F′(n−1, r−1) , where F′(n,r) is used to uniquely encode/decode a vector Xcc and wherein function F′(n,r) is given as:
- F
- ′
-
- (
- n
- ,
- d
- )
- =
- R
- ′
-
- (
- ∑
- i
- =
- n
- -
- d
- +
- 1
- n
-
- P
- ′
-
- (
- i
- )
- -
- Q
- ′
-
- (
- d
- )
- )
- ,
- where P′(i) and Q′(r) are given as:
- P
- ′
-
- (
- i
- )
- =
- 2
- -
- 21
-
- ⌊
- 2
- 21
-
- log
- 2
-
- (
- i
- )
- +
- 1
- ⌋
- ,
- i
- ∈
- [
- 1
- ,
- 2
- ,
- …
-
- ,
- 144
- ]
- and
- Q
- ′
-
- (
- r
- )
- =
- {
-
- 0
- ,
-
- r
- =
- 1
- ∑
- j
- =
- 2
- r
-
- 2
- -
- 14
-
- ⌊
- 2
- 14
-
- log
- 2
-
- (
- j
- )
- -
- 1
- ⌋
- ,
-
- r
- ∈
- [
- 2
- ,
- …
-
- ,
- 28
- ]
- ,
- and where R(k) is an approximation of function R′(k)≈2k, given as:
- R′(k)=└2kt−19└219Kf┘┘,
- where k=ki +kf is broken down into integer and fractional components of k, and Kf=2kf is a Taylor series expansion of a fractional component of k;
- and
- decoder circuitry receiving F′(n,r) and a codeword and outputting a speech, audio, image, or video signals based on the codeword and F′(n,r).
131 more elements
Dependencies are inferred from the claim text.