Methods and Systems for Error-Correction in Convolutional and Systematic Convolutional Decoders in Galois Configuration
Convolutional coders having an n-state with n≧2 Linear Feedback Shift Registers (LFSR) in Galois configuration with k shift register elements with k>1 are provided. Corresponding decoders are also provided. A convolutional coder generates a sequence of coded n-state symbols. A content of a starting position of an LFSR in a decoder is determined when sufficient error free coded symbols are available. Up to k symbols in error are corrected. A systematic convolutional coder and decoder are also provided.
1 . A method for decoding with a processor a first coded sequence of p n-state symbols with p and n being integers greater or equal to 2, comprising:
generating the first coded sequence from a second sequence of p n-state symbols by a first coder associated with a first n-state Linear Feedback Shift Register (LFSR) in Galois configuration with k shift register elements, k being an integer greater than 1, each n-state symbol in the first coded sequence being represented by a signal;
determining a start state of a first decoder corresponding to the first coder by processing at least k symbols of the first coded sequence and at least k symbols of a third sequence related to the second sequence; and
decoding the first coded sequence into a first decoded sequence with the first decoder by applying the start state.
2 . The method as claimed in claim 1 , wherein the third sequence is identical to the second sequence.
3 . The method as claimed in claim 1 , wherein:
the third sequence is generated from the second sequence by a second coder associated with a second n-state Linear Feedback Shift Register (LFSR) having at least k shift register elements; and
determining a start state of the first decoder by processing at least 2*k symbols of the first sequence and at least 2*k symbols of the third sequence.
4 . The method as claimed in claim 1 , further comprising:
storing a first state of the first decoder when corresponding symbols in the first coded sequences and the second sequence indicate an error; and
correcting up to k n-state symbols in error in a sequence of n-state symbols by processing the first state and the start state by the processor.
5 . The method as claimed in claim 1 , wherein an n-state symbol is represented by an n-state signal able to assume one of n states.
6 . The method as claimed in claim 1 , wherein an n-state symbol is represented by a binary word, and a decoder is implemented by using binary circuitry.
7 . The method as claimed in claim 1 , wherein n>2.
8 . The method as claimed in claim 1 , wherein the method is applied in a communication system.
9 . The method as claimed in claim 1 , wherein the method is applied in a data storage system.
10 . A method for decoding with a processor a first coded sequence of p n-state symbols with p and n being integers greater or equal to 2, comprising:
generating the first coded sequence from an uncoded sequence of p n-state symbols by a first coder equivalent to a first n-state descrambler with a first n-state Linear Feedback Shift Register (LFSR) in Fibonacci configuration having k shift register elements with k being an integer greater than 1;
determining a start state of a first decoder corresponding to the first coder by processing k symbols of the first coded sequence and k symbols of the uncoded sequence; and
decoding the first coded sequence into a first decoded sequence with the first decoder by applying the start state.
11 . A system for decoding a first coded sequence of p n-state symbols with p and n being integers greater or equal to 2, comprising:
a memory for storing and retrieving data and instructions;
a processor for executing instructions to performs the steps of:
generating the first coded sequence from an uncoded sequence of p n-state symbols by a first coder associated with a first n-state Linear Feedback Shift Register (LFSR) in Galois configuration having k shift register elements with k being an integer greater than 1;
determining a start state of a first decoder corresponding to the first coder by processing at least k symbols of the first coded sequence and at least k symbols of a second sequence related to the uncoded sequence; and
decoding the first coded sequence into a first decoded sequence with the first decoder by applying the start state.
12 . The system as claimed in claim 11 , wherein the second sequence is the uncoded sequence.
13 . The system as claimed in claim 11 , wherein:
the second sequence is generated from the uncoded sequence by a second coder associated with a second n-state Linear Feedback Shift Register (LFSR) having at least k shift register elements with k being an integer greater than 1; and
determining a start state of the first decoder by processing at least 2*k symbols of the first coded sequence and at least 2*k symbols of the second sequence.
14 . The system as claimed in claim 11 , further comprising instructions to perform:
storing a first state of the first decoder when corresponding symbols in the first coded sequences and the second sequence indicate an error; and
correcting up to k n-state symbols in error in a sequence of n-state symbols by processing the first state and the start state by the processor.
15 . The system as claimed in claim 11 , wherein an n-state symbol is represented by an n-state signal able to assume one of n states.
16 . The system as claimed in claim 11 , wherein an n-state symbol is represented by a binary word, and a decoder is implemented by using binary circuitry.
17 . The system as claimed in claim 11 , wherein n>2.
18 . The system as claimed in claim 11 , wherein the system is part of a communication system.
19 . The system as claimed in claim 11 , wherein the system is part of a wireless communication system.
20 . The system as claimed in claim 1 , wherein the system is applied in a data storage system.