System and method for joint source-channel encoding, with symbol decoding and error correction

• US 20020016945A1
• Filed: 03/24/2001
• Published: 02/07/2002
• Est. Priority Date: 03/27/2000
• Status: Active Grant

• Current Assignee: Board of Regents of the University of Nebraska
• Original Assignee: Board of Regents of the University of Nebraska
• Inventors: Sayood, Khalid, Hoffman, Michael W., Pettijohn, Billy D.
• Granted Patent: US 6,892,343 B2
• Time in Patent Office: Days
• US Class Current: 714/779
• CPC Class Codes: H03M 13/07 Arithmetic codes
• CPC Class Codes: H03M 13/47 Error detection, forward error correction or error protection, not provided for in groups H03M13/01 - H03M13/37
• CPC Class Codes: H03M 13/6312 Error control coding in combination with data compression
• CPC Class Codes: H03M 7/4006 Conversion to or from arithmetic code
• CPC Class Codes: H04L 1/0054 Maximum-likelihood or sequential decoding, e.g. Viterbi, Fano, ZJ algorithms
• CPC Class Codes: H04L 1/0056 Systems characterized by the type of code used H04L1/08 takes precedence

Abstract

Disclosed is a system and method for joint source-channel encoding, symbol decoding and error correction, preferably utilizing an arithmetic encoder with operational error detection space; and a combination sequential, and arithmetic, encoded symbol decoder means.

Claims

1. A variable length symbol, joint source-channel encoding, symbol decoding and error correction system comprising:

encoder system;

modulation-transmission means; and

combination sequential, and encoded symbol, decoding systems;

said encoder system comprising input means for accepting a sequential plurality of allowed input symbols and output means for outputting an encoded sequence of bits for allowed symbols input thereinto;

said encoder system being functionally interconnected to said modulation-transmission means such that entry of a symbol to said encoder system results in said encoder means outputting an encoded sequence of bits therefore into said modulation-transmission means;

said modulation-transmission means and combination sequential, and encoded symbol, decoding systems being functionally interconnected such that an encoded symbol sequence of bits entered to said modulation-transmission means enters said combination sequential, and encoded symbol, decoding systems;

said sequential decoding system comprising a plurality of bistable elements;

said encoded symbol decoding system comprising means for initiating an error correction routine to the end that, upon the detecting of the presence of an unexpected encoded reserved symbol a selection from the group consisting of;

at least one bistable element in said sequential decoding means is changed; and

selection is made of a series of sequential bits, said selection being made from a group consisting of a plurality of such series of sequential bits which result from the changing of bistable elements in said sequential decoder means;

is performed;

wherein said reserved symbol is not allowed as an input symbol to said symbol encoding system.

2. A variable length symbol joint source-channel encoding, symbol decoding and error correction system comprising:

encoder means;

modulation-transmission means; and

combination sequential, and encoded symbol, decoding means;

said encoder means comprising input means for accepting a sequential plurality of allowed input symbols and output means for outputting an encoded sequence of bits for allowed symbols input thereinto;

said encoder means further having means for generating, and in a sequence expected by said encoded symbol decoding means, outputting an encoded sequence of bits for at least one reserved symbol before and/or after an encoded allowed input symbol, which reserved symbol is not allowed as an input symbol to said encoder means input means;

said encoder means being functionally interconnected to said modulation-transmission means such that entry of a symbol to said encoder means results in said encoder means outputting an encoded sequence of bits therefore into said modulation-transmission means;

said modulation-transmission means and combination sequential, and encoded symbol, decoding means being functionally interconnected such that an encoded symbol sequence of bits entered to said modulation-transmission means enters said encoded symbol decoding means;

said sequential decoding means comprising a plurality of bistable elements;

said encoded symbol decoding means comprising means for initiating an error correction routine to the end that, upon the detecting of the presence of an unexpected encoded reserved symbol, or the absence of an expected encoded sequence of bits for a reserved symbol, a selection from the group consisting of;

at least one bistable element in said sequential decoding means is changed; and

selection is made of a series of sequential bits, said selection being made from a group consisting of a plurality of such series of sequential bits which result from the changing of bistable elements in said sequential decoder means;

is performed.

3. A joint source-channel encoding, symbol decoding and error correction system comprising:

encoder means;

modulation-transmission means; and

decoding means;

wherein said encoder means comprises input means for accepting a sequential plurality of allowed input symbols and output means for outputting an encoded sequence of bits for allowed symbols input thereinto;

wherein said decoding means comprises a functional combination of a sequential decoder means which comprises a sequence of bistable elements, each of which can be set to represent encoded symbol bits, and an encoded symbol decoder means;

said encoder means being functionally interconnected to said modulation-transmission means and said modulation-transmission means being functionally interconnected to said decoding means;

such that in use said encoder means receives a sequence of allowed symbols at its input means and provides an encoded sequence of bits for at least some thereof, said sequence of bits being caused to arrive at said decoding means;

and said encoded symbol decoder means having error detection means such that in use said encoded symbol decoder means, upon detecting the presence of an unexpected encoded sequence of bits for reserved symbol, initiates an error correction routine to the end that a selection from the group consisting of;

at least one bistable element in said sequential decoding means is changed; and

selection is made of a series of sequential bits, said selection being made from a group consisting of a plurality of such series of sequential bits which result from the changing of bistable elements in said sequential decoder means;

is performed;

wherein said reserved symbol is not allowed as an input symbol to said symbol encoding means.

4. A joint source-channel encoding, symbol decoding and error correction system as in claim 3 in which said encoder means is an arithmetic encoder and said decoding means comprises, as the encoded symbol decoder means, an arithmetic decoder.

5. A joint source-channel encoding, symbol decoding and error correction system comprising:

encoder means;

modulation-transmission means; and

decoding means;

wherein said decoding means comprises a functional combination of a sequential decoder means which comprises a sequence of bistable elements, each of which can be set to represent encoded symbol bits, and an encoded symbol decoder means;

wherein said encoder means comprises input means for accepting a sequential plurality of allowed input symbols and output means for outputting an encoded sequence of bits for allowed symbols input thereinto, said encoder means further having means for generating and, in a sequence expected by said encoded symbol decoder means, outputting an encoded sequence of bits for at least one reserved symbol before and/or after an encoded allowed input symbol, which reserved symbol is not allowed as an input symbol to said encoder means input means;

said encoder means being functionally interconnected to said modulation-transmission means and said modulation-transmission means being functionally interconnected to said decoding means;

such that in use said encoder means receives a sequence of allowed symbols at its input means and provides an encoded sequence of bits for at least some thereof in optional combination with a sequence of bits which represent at least one encoded reserved symbol in a pattern expected by said decoder means, said sequence of bits being caused to arrive at said decoding means;

and said encoded symbol decoder means having error detection means such that in use said encoded symbol decoder means, upon detecting the absence of an expected encoded reserved symbol, or the presence of an unexpected encoded reserved symbol, initiates an error correction routine to the end that a selection from the group consisting of;

at least one bistable element in said sequential decoding means is changed; and

selection is made of a series of sequential bits, said selection being made from a group consisting of a plurality of such series of sequential bits which result from the changing of bistable elements in said sequential decoder means;

is performed.

6. A joint source-channel encoding, symbol decoding and error correction system as in claim 5 in which said encoder means is an arithmetic encoder and said decoding means comprises, as the encoded symbol decoder means, an arithmetic decoder.

7. A joint source-channel encoding, symbol decoding and error correction system comprising:

arithmetic encoder system;

modulation-transmission means; and

decoding system;

wherein said arithmetic encoder system comprises input means for accepting a sequential plurality of allowed input symbols and output means for outputting an encoded sequence of bits for allowed symbols input thereinto;

wherein said decoding system comprises a functional combination of a sequential decoder system which comprises a sequence of bistable elements, each of which can be set to represent encoded symbol bits, and an arithmetic decoder system;

said arithmetic encoder system being functionally interconnected to said modulation-transmission means and said modulation-transmission means being functionally interconnected to said decoding system;

such that in use said arithmetic encoder system receives a sequence of allowed symbols at its input means and provides an encoded sequence of bits for at least some thereof, said sequence of bits being caused to arrive at said decoding system;

and said arithmetic decoder system having error detection means such that in use said arithmetic decoder system, upon detecting the presence of an unexpected encoded reserved symbol, initiates an error correction routine to the end that a selection from the group consisting of;

at least one bistable element in said sequential decoding means is changed; and

selection is made of a series of sequential bits, said selection being made from a group consisting of a plurality of such series of sequential bits which result from the changing of bistable elements in said sequential decoder means;

is performed;

wherein said reserved symbol is not allowed as an input symbol to said symbol encoding system.

8. A joint source-channel encoding, symbol decoding and error correction system comprising:

arithmetic encoder means;

modulation-transmission means; and

decoding means;

wherein said decoding means comprises a functional combination of a sequential decoder means which comprises a sequence of bistable elements, each of which can be set to represent encoded symbol bits, and an arithmetic decoder means;

wherein said arithmetic encoder means comprises input means for accepting a sequential plurality of allowed input symbols and output means for outputting an encoded sequence of bits for allowed symbols input thereinto, said arithmetic encoder means further having means for generating and, in a sequence expected by said arithmetic decoder means, outputting an encoded sequence of bits for at least one reserved symbol before and/or after an encoded allowed input symbol, which reserved symbol is not allowed as an input symbol to said arithmetic encoder means input means;

said arithmetic encoder means being functionally interconnected to said modulation-transmission means and said modulation-transmission means being functionally interconnected to said decoding means;

such that in use said arithmetic encoder means receives a sequence of allowed symbols at its input means and provides an encoded sequence of bits for at least some thereof in optional combination with at least one encoded reserved symbol in a pattern expected by said arithmetic decoder means, said sequence of bits being caused to arrive at said decoding means;

and said arithmetic decoder means having error detection means such that in use said arithmetic decoder means, upon detecting the absence of an expected encoded reserved symbol, or the presence of an unexpected encoded reserved symbol, initiates an error correction routine to the end that a selection from the group consisting of;

at least one bistable element in said sequential decoding means is changed; and

selection is made of a series of sequential bits, said selection being made from a group consisting of a plurality of such series of sequential bits which result from the changing of bistable elements in said sequential decoder means;

is performed;

wherein said reserved symbol is not allowed as an input symbol to said symbol encoding system.

9. A method of correcting errors in decoded symbols which are encoded by an encoder means in a joint source-channel coding system, comprising the steps of:

a. providing a joint source-channel encoding, symbol decoding and error correction system comprising;

encoder means;

modulation-transmission means; and

decoding means;

wherein said decoding means comprises a functional combination of a sequential decoder means which comprises a sequence of bistable elements, each of which can be set to represent encoded symbol bits, and an encoded symbol decoder means;

wherein said encoder means comprises input means for accepting a sequential plurality of allowed input symbols and output means for outputting an encoded sequence of bits for allowed symbols input thereinto, said encoder means further having means for generating and, in a sequence expected by said encoded symbol decoder means, outputting an encoded sequence of bits for at least one reserved symbol before and/or after an encoded allowed input symbol, which reserved symbol is not allowed as an input symbol to said encoder means input means;

said encoder means being functionally interconnected to said modulation-transmission means and said modulation-transmission means being functionally interconnected to said decoding means;

such that in use said encoder means receives a sequence of allowed symbols at its input means and provides an encoded sequence of bits for at least some thereof, in optional combination with at least one encoded reserved symbol in a pattern expected by said decoder means, said sequence of bits being caused to arrive at said decoding means;

and said encoded symbol decoder means having error detection means such that in use said encoded symbol decoder means, upon detecting the absence of an expected encoded reserved symbol, or the presence of an unexpected encoded reserved symbol, initiates an error correction routine to the end that a selection from the group consisting of;

at least one bistable element in said sequential decoding means is changed; and

selection is made of a series of sequential bits, said selection being made from a group consisting of a plurality of such series of sequential bits which result from the changing of bistable elements in said sequential decoder means;

is performed;

b. inputting a plurality of symbols to the input means of said encoder means;

c. causing said encoder means to encode at least some of said plurality of symbols and output bits corresponding thereto into said modulation-transmission means;

d. causing said modulation-transmission means to enter said at least some of said plurality of encoded symbols into said functional combination of said sequential decoder means and encoded symbol decoder means;

e. causing said encoded symbol decoder means to, if detecting a present unexpected or absent expected, encoded reserved symbol, perform a selection from the group consisting of;

change at least one bistable element in said sequential decoder means; and

select a series of sequential bits, said selection being made from a group consisting of a plurality of such series of sequential bits which result from the changing of bistable elements in said sequential decoder means.

10. A method of correcting errors in decoded symbols which are encoded by an arithmetic encoder in a joint source-channel coding system, comprising the steps of:

a. providing a joint source-channel encoding, symbol decoding and error correction system comprising;

arithmetic encoder means;

modulation-transmission means; and

decoding means;

wherein said arithmetic encoder means comprises input means for accepting a sequential plurality of allowed input symbols and output means for outputting an encoded sequence of bits for allowed symbols input thereinto;

wherein said decoding means comprises a functional combination of a sequential decoder means which comprises a sequence of bistable elements, each of which can be set to represent encoded symbol bits, and an arithmetic decoder means;

said arithmetic encoder means being functionally interconnected to said modulation-transmission means and said modulation-transmission means being functionally interconnected to said decoding means;

such that in use said arithmetic encoder means receives a sequence of allowed symbols at its input means and provides an encoded sequence of bits for at least some thereof, said sequence of bits being caused to arrive at said decoding means;

and said arithmetic decoder means having error detection means such that in use said arithmetic decoder means, upon detecting the presence of an unexpected encoded reserved symbol, initiates an error correction routine to the end that a selection from the group consisting of;

at least one bistable element in said sequential decoding means is changed; and

selection is made of a series of sequential bits, said selection being made from a group consisting of a plurality of such series of sequential bits which result from the changing of bistable elements in said sequential decoder means;

is performed;

wherein said reserved symbol is not allowed as an input symbol to said symbol encoding system;

b. inputting a plurality of symbols to the input means of said arithmetic encoder means;

c. causing said arithmetic encoder means to encode at least some of said plurality of symbols and output bits corresponding thereto into said modulation-transmission means;

d. causing said modulation-transmission means to enter said at least some of said plurality of encoded symbols into said functional combination of said sequential decoder means and arithmetic decoder means;

e. causing said arithmetic decoder means to, if detecting a present unexpected encoded reserved symbol perform a selection from the group consisting of;

change at least one bistable element in said sequential decoder means; and

select a series of sequential bits, said selection being made from a group consisting of a plurality of such series of sequential bits which result from the changing of bistable elements in said sequential decoder means.

11. A method of correcting errors in decoded symbols which are encoded by an arithmetic encoder in a joint source-channel coding system, comprising the steps of:

a. providing a joint source-channel encoding, symbol decoding and error correction system comprising;

arithmetic encoder means;

modulation-transmission means; and

decoding means;

wherein said decoding means comprises a functional combination of a sequential decoder means which comprises a sequence of bistable elements, each of which can be set to represent encoded symbol bits, and an arithmetic decoder means;

wherein said arithmetic encoder means comprises input means for accepting a sequential plurality of allowed input symbols and output means for outputting an encoded sequence of bits for allowed symbols input thereinto, said arithmetic encoder means further having means for generating and, in a sequence expected by said arithmetic decoder means, outputting an encoded sequence of bits for at least one reserved symbol before and/or after an allowed input symbol, which reserved symbol is not allowed as an input symbol to said arithmetic encoder means input means;

said arithmetic encoder means being functionally interconnected to said modulation-transmission means and said modulation-transmission means being functionally interconnected to said decoding means;

such that in use said arithmetic encoder means receives a sequence of allowed symbols at its input means and provides an encoded sequence of bits for at least some thereof in optional combination with at least one encoded reserved symbol in a pattern expected by said arithmetic decoder means, said sequence of bits being caused to arrive at said decoding means;

and said arithmetic decoder means having error detection means such that in use said arithmetic decoder means, upon detecting the absence of an expected encoded reserved symbol, or the presence of an unexpected encoded reserved symbol, initiates an error correction routine to the end that a selection from the group consisting of;

at least one bistable element in said sequential decoding means is changed; and

selection is made of a series of sequential bits, said selection being made from a group consisting of a plurality of such series of sequential bits which result from the changing of bistable elements in said sequential decoder means;

is performed;

wherein said reserved symbol is not allowed as an input symbol to said symbol encoding system;

b. inputting a plurality of symbols to the input means of said arithmetic encoder means;

c. causing said arithmetic encoder means to encode at least some of said plurality of symbols and output bits corresponding thereto, optionally intermingled with arithmetic at least one encoder means generated reserved symbol, into said modulation-transmission means;

d. causing said modulation-transmission means to enter said at least some of said plurality of encoded symbols, optionally along with at least one encoded reserved symbol entered into said modulation-transmission means, into said functional combination of said sequential decoder means and arithmetic decoder means;

e. causing said arithmetic decoder means to, if detecting a non-present expected or present unexpected encoded reserved symbol, perform a selection from the group consisting of;

change at least one bistable element in said sequential decoder means; and

select a series of sequential bits, said selection being made from a group consisting of a plurality of such series of sequential bits which result from the changing of bistable elements in said sequential decoder means.

13. A method of correcting errors in decoded symbols as in claim 12, in which in step d. involves the determination of the presence or absence of non-alphabet symbols other than as expected, said non-alphabet symbols being not-allowed as arithmetic encoder input symbols.

14. A method of correcting errors in decoded symbols as in claim 12, which comprises practicing step d. more than once, with said error correcting method further comprising the step of:

e. defining a tolerable Hamming distance threshold Tc, and keeping count of the number Kc of “

branch points”

in said sequential decoder means at which correction of the “

1”

/(“

0”

) or “

0”

/(“

1”

) based binary bit thereat by inverting to “

0”

/(“

1”

) or “

1”

/(“

0”

) has been performed; and

if Kc exceeds Tc, expanding the null zone by increasing the magnitude of Δ

, thereby making available additional “

branch points”

.

15. A method of correcting errors in decoded symbols as in claim 14, said error correction method further comprising the step of:

f. determining in a second or greater practice of step e. if the identified “

branch point”

is sequentially prior to the “

branch point”

identified in the immediately previous practice of step e. and if so decreasing the value of Kc by 1, otherwise increasing the value of Kc by 1.

16. A method of correcting errors in decoded symbols as in claim 12, which comprises practicing step d. more than once, with said error correcting method further comprising the step of:

e. defining a means for calculating a Euclidean distance between received and decoded symbols, and a tolerable rate of increase of Euclidean distance between sequential practice of step d., and

if said Euclidean distance increases faster than at said tolerable rate, expanding the null zone by increasing the magnitude of Δ

, thereby making available additional “

branch points”

.

18. A method of correcting errors in decoded symbols as in claim 17 in which the step e. determination of which series of sequential bits in said produced plurality of series of sequential bits is most likely correct, involves at least one selection from the group consisting of:

a. eliminating any series of sequential bits which contains an encoded reserved symbol;

b. applying a metric to at least two series of sequential bits which do not contain an encoded reserved sysbol, to determine which of said at least two series of sequential bits is most likely correct;

c. applying an Euclidean metric to at least two series of sequential bits which do not contain an encoded reserved sysbol, to determine which of said at least two series of sequential bits is most likely correct.

12. A method of correcting errors in decoded symbols which are encoded by an arithmetic encoder in a joint source-channel coding system, comprises the steps of:

a. providing a joint source-channel encoding, symbol decoding and error correction, system comprising;

arithmetic encoder means;

modulation-transmission means; and

decoding means;

wherein said decoding means comprises a functional combination of a sequential decoder means which comprises a sequence of bistable elements, each of which can be set to represent encoded symbol bits, and an arithmetic decoder means;

wherein said arithmetic encoder means comprises input means for accepting a sequential plurality of allowed input symbols and output means for outputting an encoded sequence of bits for allowed symbols input thereinto, said arithmetic encoder means further having means for generating and, in a sequence expected by said arithmetic decoder means, outputting an encoded sequence of bits for at least one reserved symbol before and/or after an encoded allowed input symbol, which reserved symbol is not allowed as an input symbol to said arithmetic encoder means input means;

said arithmetic encoder means being functionally interconnected to said modulation-transmission means and said modulation-transmission means being functionally interconnected to said decoding means;

such that in use said arithmetic encoder means receives a sequence of allowed symbols at its input means and provides an encoded sequence of bits for at least some thereof in optional combination with at least one encoded reserved symbol in a pattern expected by said arithmetic decoder means, said sequence of bits being caused to arrive at said decoding means;

and said arithmetic decoder means having error detection means such that in use said arithmetic decoder means, upon detecting the absence of an expected encoded reserved symbol, or the presence of an unexpected encoded reserved symbol, initiates an error correction routine to the end that at least one bistable element in said sequential decoder means is changed;

b. entering a sequence of symbols into said arithmetic encoder such that said sequence of symbols are encoded and exited therefrom as a binary bit stream sequence of +x{square root}{square root over (Es)} and −

x{square root}{square root over (Es)} signals, corresponding to a string of “

1”

/(“

0”

)'"'"'s and “

0”

/(“

1”

)'"'"'s which pass through said transmission channel and enter said sequential decoder means, where x is a fraction;

c. making hard logic circuitry decisions as to the presence of “

1”

/(“

0”

)'"'"'s and “

0”

/(“

1”

)'"'"'s based on said binary bit stream sequence of +x{square root}{square root over (Es)} and −

x{square root}{square root over (Es)} signals while identify decisions based upon signals wherein x is of a value so as to cause the values of +x{square root}{square root over (Es)} or −

x{square root}{square root over (Es)} to be within a null zone of +Δ

to −

Δ

around 0.0, and identifying said decisions as “

branch point”

decisions in said sequential decoder means;

d. monitoring output from said arithmetic decoder for errors and when an error is indicated thereby, identifying a “

branch point”

in said sequential decoder means and correcting the “

1”

/(“

0”

) or “

0”

/(“

1”

) based binary bit thereat by inverting it to “

0”

/(“

1”

) or “

1”

/(“

0”

).

17. A method of correcting errors in decoded symbols which are encoded by an arithmetic encoder in a joint source-channel coding system, comprises the steps of:

a. providing a joint source-channel encoding, symbol decoding and error correction system comprising;

arithmetic encoder means;

modulation-transmission means; and

decoding means;

wherein said decoding means comprises a functional combination of a sequential decoder means which comprises a sequence of bistable elements, each of which can be set to represent encoded symbol bits, and an arithmetic decoder means;

specific bistable elements in said sequential decoder means being identified as fixed branch points;

wherein said arithmetic encoder means comprises input means for accepting a sequential plurality of allowed input symbols and output means for outputting an encoded sequence of bits for allowed symbols input thereinto, said arithmetic encoder means further having means for generating and, in a sequence expected by said arithmetic decoder means, outputting an encoded sequence of bits for at least one reserved symbol before and/or after an encoded allowed input symbol, which reserved symbol is not allowed as an input symbol to said arithmetic encoder means input means;

said arithmetic encoder means being functionally interconnected to said modulation-transmission means and said modulation-transmission means being functionally interconnected to said decoding means;

such that in use said arithmetic encoder means receives a sequence of allowed symbols at its input means and provides an encoded sequence of bits for at least some thereof in optional combination with at least one encoded reserved symbol in a pattern expected by said arithmetic decoder means, said sequence of bits being caused to arrive at said decoding means;

and said arithmetic decoder means having error detection means such that in use said arithmetic decoder means, upon detecting the absence of an expected encoded reserved symbol, or the presence of an unexpected encoded reserved symbol, initiates an error correction routine to the end that;

selection is made of a series of sequential bits, said selection being made from a group consisting of a plurality of such series of sequential bits which result from the changing of bistable elements in said sequential decoder means at said specified branch points;

is performed;

b. entering a sequence of symbols into said arithmetic encoder means such that said sequence of symbols are encoded and exited therefrom as a binary bit stream sequence;

c. monitoring output from said arithmetic decoder means for errors;

d. upon detection of an error by said arithmetic decoder means, producing a plurality of series of sequential bits which result from the changing of bistable elements in said sequential decoder means at said branch points by using fixed branch point bistable elements in said sequential decoder means;

e. determining which series of sequential bits in said produced plurality of series of sequential bits is most likely correct.