Back to results
US 8,572,470 B2Granted
Memory-efficient storage method: a fast BJCR based decoder implementation scheme
AssigneeNXP B.V.
InventorsJianho Hu, Feng Li, Hong Wen
Life of this patent
Estimating the term…
Abstract
A memory efficient, accelerated implementation architecture for BCJR based forward error correction algorithms. In this architecture, a memory efficiency storage scheme is adopted for the metrics and channel information to achieve high processing speed with a low memory requirement. Thus, BCJR based algorithms can be accelerated, and the implementation complexity can be 5 reduced. This scheme can be used in the BCJR based turbo decoder and LDPC decoder implementations.
Claims9
A method of decoding a turbo code by a decoder implementing the Balh-Cocke-Jelinek-Raviv (BCJR) algorithm, the method comprising:
- a) iteratively calculating forward metrics and backward metrics according to maximum a posteriori (MAP) type algorithm;
- b) storing each of the forward metrics as they are calculated in sequence beginning from a head position of a memory unit having a plurality of storage locations equal in number to a length of the turbo code, wherein the plurality of storage locations are initially unloaded with any of the forward metrics or the backward metrics;
- c) storing each of the backward metrics as they are calculated in sequence beginning from a tail position of the memory unit;
- d) after a number of the forward metrics and a number of the backward metrics fill up all of the initially unloaded storage locations of the memory unit, iteratively calculating a plurality of extrinsic information corresponding to the forward metrics and the backward metrics stored in the memory unit,
- wherein at least one of the forward metrics already used for calculating its corresponding one of the plurality of extrinsic information is overwritten in its corresponding storage location by one of the backward metrics calculated after the at least one of the forward metrics, and
- wherein at least one of the backward metrics already used for calculating its corresponding one of the plurality of extrinsic information is overwritten in its corresponding storage location by one of the forward metrics calculated after the at least one of the backward metrics.
3 more elements
A method of decoding a received message comprising L symbols according to a BCJR MAP algorithm, the method comprising:
- calculating forward metrics αk corresponding to metrics of the MAP decoder in a forward direction at a kth step, according to an equation:
- α
- k
-
- (
- s
- )
- =
- ∑
- s
- ′
-
- α
- k
- -
- 1
-
- (
- s
- ′
- )
-
- γ
- k
-
- (
- s
- ′
- ,
- s
- )
- ∑
- s
-
- ∑
- s
- ′
-
- α
- k
- -
- 1
-
- (
- s
- ′
- )
-
- γ
- k
-
- (
- s
- ′
- ,
- s
- )
- ,
- wherein sεS, and s′εS, wherein S is a state space of a turbo code, and wherein α0 is known, and probability γk(s′, s) is defined as:
- γ
- k
-
- (
- s
- ′
- ,
- s
- )
- =
- p
-
- (
- s
- k
- =
- s
- /
- s
- k
- -
- 1
- =
- s
- ′
- )
- =
- exp
-
- [
- 1
- 2
-
- x
- k
-
- (
- LLe
- k
- +
- L
- c
-
- ds
- k
- s
- )
- +
- 1
- 2
-
- L
- c
-
- dp
- k
-
- Y
- k
- ]
- =
- exp
-
- [
- 1
- 2
-
- x
- k
-
- (
- LLe
- k
- +
- L
- c
-
- ds
- k
- s
- )
- ]
- +
- γ
- k
- e
-
- (
- s
- ′
- ,
- s
- )
- ,
- wherein xk is a kth symbol at a decoding path, γk is a kth parity code word at a decoding path, LLek is extrinsic information of the MAP decoder for the kth symbol, dp is a kth parity code word fed into the decoder, and ds is a kth symbol fed into the decoder;
- calculating backward metrics βk−1 corresponding to metrics of the MAP decoder in a reverse direction at the kth step, according to an equation:
- β
- k
- -
- 1
-
- (
- s
- )
- =
- ∑
- S
-
- β
- k
-
- (
- s
- )
-
- γ
- k
-
- (
- s
- ′
- ,
- s
- )
- ∑
- s
-
- ∑
- s
- ′
-
- α
- k
- -
- 1
-
- (
- s
- ′
- )
-
- γ
- k
-
- (
- s
- ′
- ,
- s
- )
- ,
- wherein βL is known;
- storing the forward metrics αk as they are calculated, in sequence beginning at a head of a memory stack, the memory stack comprising memory units M0, M1, M2, . . . , ML from head to tail, respectively;
- storing backward metrics βk as they are calculated, in reverse sequence beginning at the tail of the memory stack;
- after h+1 forward metrics α0−αh and h backward metrics βL−βh+1 are stored in the memory stack, wherein h=(L−1)/2, calculating extrinsic information LLek according to an equation:
- LLe
- k
- =
- ∑
- s
- +
-
- α
- k
- -
- 1
-
- (
- s
- ′
- )
-
- γ
- e
-
- (
- s
- ′
- ,
- s
- )
-
- β
- k
-
- (
- s
- )
- ∑
- s
- -
-
- α
- k
- -
- 1
-
- (
- s
- ′
- )
-
- γ
- e
-
- (
- s
- ′
- ,
- s
- )
-
- β
- k
-
- (
- s
- )
- ,
- wherein s+ corresponds to a sub-collection of the states transfer from s′ to s, (s′→s), when xk=+1, and
- wherein s− corresponds to a sub-collection of the states transfer from s to s′, (s→s′), when xk=−1;
- storing further forward metrics αh+1−αL in sequence in the memory stack to overwrite the backward metrics stored in those spaces after the extrinsic information LLek is calculated using those backward metrics;
- and
- storing further backward metrics βh−β0 in reverse sequence in the memory stack to overwrite the forward metrics stored in those spaces after the extrinsic information LLek is calculated using those forward metrics.
280 more elements
Dependencies are inferred from the claim text.