Methods and apparatus for search sphere linear block decoding
View Patent ↗A search sphere-based linear block decoder is provided. A received vector, v, is decoded by computing a syndrome vector, S, corresponding to the received vector, v; (S=vH); obtaining a set of all possible error vectors, e, corresponding to the computed syndrome vector, S, wherein the set of all possible error vectors, e, is obtained from a pre-computed error table and has a specified maximum number of bit errors; calculating a set of all possible received vectors, x, based on the received vector, v, and the set of all possible error vectors, e; determining a k-bit code-vector x that is closest to the received vector, v; and determining an n-bit data-vector, d, associated with the k-bit code-vector x. The pre-computed error table can be generated by multiplying all possible error vectors by a Syndrome Matrix, to obtain all possible syndrome vectors associated with all possible error vectors.
1. A method for decoding a received vector, v, comprising:
obtaining said received vector, v;
computing a syndrome vector, S, corresponding to said received vector, v;
S=vH
obtaining a set of all possible error vectors, e, corresponding to said computed syndrome vector, S, wherein said set of all possible error vectors, e, is obtained from a pre-computed error table and has a specified maximum number of bit errors;
calculating a set of all possible received vectors, x, based on said received vector, v, and said set of all possible error vectors, e,
determining a k-bit code-vector x that is closest to said received vector, v; and
determining an n-bit data-vector, d, associated with the k-bit code-vector x.
2. The method of claim 1 , wherein said computing step computes said syndrome vector S, as follows:
S=vH
where H is a parity check matrix.
3. The method of claim 1 , wherein said pre-computed error table is generated by multiplying all possible error vectors by a Syndrome Matrix, to obtain all possible syndrome vectors associated with all possible error vectors.
4. The method of claim 3 , wherein said pre-computed error table provides a search sphere of possible error vectors around said received vector.
5. The method of claim 1 , wherein said step of determining said k-bit code-vector x that is closest to said received vector, v, applies a maximum likelihood criterion.
6. The method of claim 1 , wherein said set of all possible received vectors, x, is calculated as follows:
x=XOR ( v,e ).
7. The method of claim 1 , wherein said determined k-bit code-vector x is closest in a Euclidian sense to said received vector, v.
8. A linear block decoder, comprising:
a memory; and
at least one hardware device, coupled to the memory, operative to:
obtain said received vector, v;
compute a syndrome vector, S, corresponding to said received vector, v;
S=vH
obtain a set of all possible error vectors, e, corresponding to said computed syndrome vector, S, wherein said set of all possible error vectors, e, is obtained from a pre-computed error table and has a specified maximum number of bit errors;
calculate a set of all possible received vectors, x, based on said received vector, v, and said set of all possible error vectors, e,
determine a k-bit code-vector x that is closest to said received vector, v; and
determine an n-bit data-vector, d, associated with the k-bit code-vector x.
9. The linear block decoder of claim 8 , wherein said syndrome vector S, is computed as follows:
S=vH
where H is a parity check matrix.
10. The linear block decoder of claim 8 , wherein said pre-computed error table is generated by multiplying all possible error vectors by a Syndrome Matrix, to obtain all possible syndrome vectors associated with all possible error vectors.
11. The linear block decoder of claim 10 , wherein said pre-computed error table provides a search sphere of possible error vectors around said received vector.
12. The linear block decoder of claim 8 , wherein said k-bit code-vector x that is closest to said received vector, v, is determined by applying a maximum likelihood criterion.
13. The linear block decoder of claim 8 , wherein said set of all possible received vectors, x, is calculated as follows:
x=XOR ( v,e ).
14. The linear block decoder of claim 8 , wherein said determined k-bit code-vector x is closest in a Euclidian sense to said received vector, v.
15. An article of manufacture for decoding a received vector, v, comprising a tangible machine readable recordable medium containing one or more programs which when executed implement the steps of:
obtaining said received vector, v;
computing a syndrome vector, S, corresponding to said received vector, v;
S=vH
obtaining a set of all possible error vectors, e, corresponding to said computed syndrome vector, S, wherein said set of all possible error vectors, e, is obtained from a pre-computed error table and has a specified maximum number of bit errors;
calculating a set of all possible received vectors, x, based on said received vector, v, and said set of all possible error vectors, e,
determining a k-bit code-vector x that is closest to said received vector, v; and
determining an n-bit data-vector, d, associated with the k-bit code-vector x.
16. The article of manufacture of claim 15 , wherein said computing step computes said syndrome vector S, as follows:
S=vH
where H is a parity check matrix.
17. The article of manufacture of claim 15 , wherein said pre-computed error table is generated by multiplying all possible error vectors by a Syndrome Matrix, to obtain all possible syndrome vectors associated with all possible error vectors.
18. The article of manufacture of claim 17 , wherein said pre-computed error table provides a search sphere of possible error vectors around said received vector.
19. The article of manufacture of claim 15 , wherein said step of determining said k-bit code-vector x that is closest to said received vector, v, applies a maximum likelihood criterion.
20. The article of manufacture of claim 15 , wherein said set of all possible received vectors, x, is calculated as follows:
x=XOR ( v,e ).