Apparatus and method for low complexity combinatorial coding and decoding of signals
View Patent ↗A method and apparatus for low complexity combinatorial coding and decoding of signals is described herein. During operation, an encoder and a decoder will utilize a first function in determining a codeword or vector when the size of the function is small. The encoder and the decoder will also utilize a second function in determining the codeword or vector when the size of the function is large.
1. A method for coding vectors within an electronic encoder, the method comprising the steps of:
creating, by a processor, a vector x at the electronic encoder from an input signal;
generating a modified combinatorial function output based on a comparison between a set of non-zero vector position p k of the vector x and a set of predetermined value p k max , wherein the modified combinatorial function output comprises either a standard combinatorial function output or an approximate combinatorial function output; and
generating a codeword C based on a set of the modified combinatorial function outputs, wherein the step of generating the modified combinatorial function output comprises:
F
^
(
p
k
,
k
)
=
{
F
(
p
k
,
k
)
,
p
k
≤
p
k
max
F
′
(
p
k
,
k
)
,
otherwise
1
≤
k
≤
v
or alternatively
F
^
(
p
k
,
k
)
=
{
F
(
p
k
,
k
)
,
p
k
+
1
-
1
≤
p
k
max
F
′
(
p
k
,
k
)
,
otherwise
1
≤
k
≤
v
wherein v is the number of elements in the set, F (p k , k) is the standard combinatorial function output, and F′(p k , k) is the approximate combinatorial function output.
2. The method of claim 1 wherein the standard combinatorial function output is expressed by
F
^
=
F
(
n
,
d
)
=
n
!
d
!
(
n
-
d
)
!
wherein n is a position parameter and d is a pulse index parameter.
3. The method of claim 1 wherein the approximate combinatorial function output comprises {circumflex over (F)}=F′(n,d)=R′(S′(n)−S′(n−d)−Q′(d)), wherein n is a position parameter, d is a pulse index parameter, R′ is an estimate of a power function, S′(n) is a log domain estimate of n! and Q′(d) is a log domain estimate of d!.
4. The method of claim 1 wherein generating a codeword C based on a set of modified combinatorial function outputs further comprises summing the set of modified combinatorial function outputs as:
C
π
=
∑
k
=
1
v
F
^
(
p
k
,
k
)
,
0
≤
p
k
<
n
wherein v is the number of elements in the set, n is a position parameter, and p k is a non-zero vector position.
5. An apparatus comprising:
a vector generator creating a vector x at an electronic encoder from an input signal;
coding circuitry using a modified combinatorial function output comprising either a standard combinatorial function output or an approximate combinatorial function output in the production of a codeword C from the vector x, wherein the standard combinatorial function output or the approximate combinatorial function output is used based on a comparison between a set of nonzero vector positions p k of the vector x and a set of predetermined values p k max , wherein the coding circuitry uses the modified combinatorial function output comprising one of:
F
^
(
p
k
,
k
)
=
{
F
(
p
k
,
k
)
,
p
k
≤
p
k
max
F
′
(
p
k
,
k
)
,
otherwise
1
≤
k
≤
v
or alternatively
F
^
(
p
k
,
k
)
=
{
F
(
p
k
,
k
)
,
p
k
+
1
-
1
≤
p
k
max
F
′
(
p
k
,
k
)
,
otherwise
1
≤
k
≤
v
wherein v is the number of elements in the set, F (p_k, k) is the standard combinatorial function output, and F′(pk, k) is the approximate combinatorial function output.
6. The apparatus of claim 5 wherein the approximate combinatorial function output comprises {circumflex over (F)}=F′(n,d)=R′(S′(n)−S′(n−d)−Q′(d)), n is a position parameter, d is a pulse index parameter, R′ is an estimate of a power function, S′(n) is a log domain estimate of n!, and Q′(d) is a log domain estimate of d!.
7. The apparatus of claim 5 wherein the standard combinatorial function output is expressed by
F
^
=
F
(
n
,
d
)
=
n
!
d
!
(
n
-
d
)
!
wherein n is a position parameter and d is a pulse index parameter.
8. A method for decoding a vector x within an electronic decoder, the method comprising the steps of:
receiving, by a processor, a codeword C at the electronic decoder;
decoding a previous non-zero position (p k+1 ) of the vector x based on the codeword;
selecting a modified combinatorial function output comprising either a standard combinatorial function output or an approximate combinatorial function output, based on the previous non-zero vector position (p k+1 ) of the vector x being less than a predetermined value;
decoding a non-zero position (pk) based on the modified combinatorial function output, wherein the modified combinatorial function output comprises one of:
F
^
(
p
k
,
k
)
=
{
F
(
p
k
,
k
)
,
p
k
≤
p
k
max
F
′
(
p
k
,
k
)
,
otherwise
1
≤
k
≤
v
or alternatively
F
^
(
p
k
,
k
)
=
{
F
(
p
k
,
k
)
,
p
k
+
1
-
1
≤
p
k
max
F
′
(
p
k
,
k
)
,
otherwise
1
≤
k
≤
v
wherein v is the number of elements in the set, F(p k ,k) is the standard combinatorial function, and F'(p k ,k) is the approximate combinatorial function.
9. The method of claim 8 wherein the approximate combinatorial function output comprises {circumflex over (F)}=F′(n,d)=R′(S′(n)−S′(n−d)−Q′(d)), wherein n is a position parameter, d is a pulse index parameter, R′ is an estimate of a power function, S′(n) is a log domain estimate of n!, and Q′(d) is a log domain estimate of d!.
10. The method of claim 8 wherein the standard combinatorial function output is expressed by
F
^
=
F
(
n
,
d
)
=
n
!
d
!
(
n
-
d
)
!
wherein n is a position parameter and d is a pulse index parameter.
11. An apparatus for decoding a vector x comprising:
decoding circuitry receiving a codeword C, using a modified combinatorial function output comprising either a standard combinatorial function output or an approximate combinatorial function output, based on the previous non-zero vector position of the vector x being less than a predetermined value, and either a first function or a second function in the production of a vector x from a codeword, wherein the first or the second function is used based on a non-zero vector position of the vector x being less than a predetermined value; and
decoding a non-zero position (pk) based on the modified combinatorial function: and
signal reconstruction circuitry creating an output signal from the vector x, wherein the decoding circuitry uses the modified combinatorial function output given by:
F
^
(
p
k
,
k
)
=
{
F
(
p
k
,
k
)
,
p
k
≤
p
k
max
F
′
(
p
k
,
k
)
,
otherwise
1
≤
k
≤
v
or alternatively
F
^
(
p
k
,
k
)
=
{
F
(
p
k
,
k
)
,
p
k
+
1
-
1
≤
p
k
max
F
′
(
p
k
,
k
)
,
otherwise
1
≤
k
≤
v
where v is the number of elements in the set, F(p k ,k) is the standard combinatorial function, and F'(p k ,k) is the approximate combinatorial function.
12. The apparatus of claim 11 wherein the approximate combinatorial function output comprises {circumflex over (F)}=F′(n,d)=R′(S′(n)−S′(n−d)−Q′(d)), wherein n is a position parameter, d is a pulse index parameter, R′ is an estimate of a power function, S′(n) is a log domain estimate of n!, and Q′(d) is a log domain estimate of d!.
13. The apparatus of claim 11 wherein the standard combinatorial function output is expressed by
F
^
=
F
(
n
,
d
)
=
n
!
d
!
(
n
-
d
)
!
wherein n is a position parameter and d is a pulse index parameter.