Apparatus and method for low complexity combinatorial coding of signals
View Patent ↗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.
1. 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)=log a (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.
2. The method of claim 1 wherein the step of generating F′(n, d) comprises the step of generating F′(n, d) such that F′(n, d)>F(n, d) and F′(n, d)>F′(n−1, d)+F′(n−1, d−1).
3. The method of claim 1 wherein 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)≈2 k , given as:
R′( k )=└2 k t −19 └2 19 K f ┘┘,
where k=k i +k f is broken down into integer and fractional components of k, and K f =2 k f is a Taylor series expansion of a fractional component of k.
4. The method of claim 1 wherein F′(n, d) is based on the function:
P′( i )=2 −l(i) └2 l(i) log a ( i )+1┘.
5. The method of claim 1 wherein F′(n, d) is based on the function:
Q
′
(
d
)
=
{
0
,
d
=
1
∑
j
=
2
d
2
-
l
(
j
)
⌊
2
l
(
j
)
log
a
(
j
)
-
1
⌋
,
d
∈
[
2
,
…
,
m
]
.
6. The method of claim 1 wherein F′(n, d) is based on the function:
R′( k )=a k t 31 l ┌a l K f ┐,
where k=k i +k f is broken down into integer and fractional components of k, and K f =α k f is a Taylor series expansion of a fractional component of k.
7. The method of claim 1 wherein a=2.
8. An apparatus comprising:
vector generator circuitry receiving a signal vector comprising speech, audio, image, or video and outputting vector X cc ;
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 X cc 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)≈2 k , given as:
R′( k )=└2 k t −19 └2 19 K f ┘┘,
where k=k i +k f is broken down into integer and fractional components of k, and K f =2 k f 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 X cc and F′(n,r).
9. 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 X cc 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)≈2 k , given as:
R′( k )=└2 k t −19 └2 19 K f ┘┘,
where k=k i +k f is broken down into integer and fractional components of k, and K f =2 k f 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).