Back to results
US 7,246,304 B2Granted
Decoding architecture for low density parity check codes
AssigneeDSP Group Ltd.
InventorSungwook Kim
Life of this patent
Estimating the term…
Abstract
Architectures for decoding low density parity check codes permit varying degrees of hardware sharing to balance throughput, power consumption and area requirements. The LDPC decoding architectures may be useful in a variety of communication systems in which throughput, power consumption, and area are significant concerns. The decoding architectures implement an approximation of the standard message passing algorithm used for LDPC decoding, thereby reducing computational complexity. Instead of a fully parallel structure, this approximation permits at least a portion of the message passing structure between check and bit nodes to be implemented in a block-serial mode, providing reduced area without substantial added latency.
Claims52
A low density parity check (LDPC) decoder comprising:
- a first computation unit that iteratively computes messages for LDPC encoded information from check nodes to bit nodes based on an approximation of the LDPC message passing algorithm, wherein the first computation unit computes at least some messages from a first one of the check nodes to one or more of the bit nodes and at least some messages from a second one of the check nodes to one or more of the bit nodes in block serial mode using shared hardware;
- and
- a second computation unit, responsive to the first computation unit, that iteratively computes messages for the LDPC encoded information from the bit nodes to the check nodes to produce a hard decoding decision.
A low density parity check (LDPC) decoder comprising:
- a first computation unit that iteratively computes messages for LDPC encoded information from check nodes to bit nodes based on an approximation of the LDPC message passing algorithm;
- and
- a second computation unit, responsive to the first computation unit, that iteratively computes messages for the LDPC encoded information from the bit nodes to the check nodes to produce a hard decoding decision, wherein the first computation unit computes the messages from check nodes to bit nodes according to an approximation of the LDPC message passing algorithm based on the following equation:
- min
- i
- ′
- ∈
- Row
-
- [
- j
- ]
-
- \
-
- {
- i
- }
-
-
- LLR
-
- (
- q
- i
- ′
-
- j
- )
-
- ·
- Π
- i
- ′
- ∈
- Row
-
- [
- j
- ]
-
- \
-
- {
- i
- }
-
- sgn
-
- (
- LLR
-
- (
- q
- i
- ′
-
- j
- )
- )
- ·
- (
- -
- 1
- )
-
- Row
-
- [
- j
- ]
-
- ,
- wherein min represents a minimum function, LLR represents a log likelihood ratio, qij represents a parity check bit value, i represents row weight of a parity check matrix, and j represents column weight of the parity check matrix.
71 more elements
A low density parity check (LDPC) decoding method comprising:
- iteratively computing messages for LDPC encoded information from check nodes to bit nodes based on an approximation of the LDPC message passing algorithm in a first computation unit, wherein at least some messages from a first one of the check nodes to one or more of the bit nodes and at least some messages from a second one of the check nodes to one or more of the bit nodes are computed in block serial mode using shared hardware;
- and
- responsive to the first computation unit, iteratively computing messages for the LDPC encoded information from the bit nodes to the check nodes to produce a hard decoding decision in a second computation unit.
A low density panty check (LDPC) decoding method comprising:
- iteratively computing messages for LDPC encoded information from check nodes to bit nodes based on an approximation of the LDPC message passing algorithm in a first computation unit;
- and
- responsive to the first computation unit, iteratively computing messages for the LDPC encoded information from the bit nodes to the check nodes to produce a hard decoding decision in a second computation unit, further comprising computing the messages from check nodes to bit nodes according to an approximation of the LDPC message passing algorithm based on the following equation:
- min
- i
- ′
- ∈
- Row
-
- [
- j
- ]
-
- \
-
- {
- i
- }
-
-
- LLR
-
- (
- q
- i
- ′
-
- j
- )
-
- ·
- Π
- i
- ′
- ∈
- Row
-
- [
- j
- ]
-
- \
-
- {
- i
- }
-
- sgn
-
- (
- LLR
-
- (
- q
- i
- ′
-
- j
- )
- )
- ·
- (
- -
- 1
- )
-
- Row
-
- [
- j
- ]
-
- ,
- wherein min represents a minimum function, LLR represents a log likelihood ratio, qi,j represents a parity check bit value, i represents row weight of a parity check matrix, and j represents column weight of the parity check matrix.
71 more elements
A low density parity check (LDPC) decoder comprising:
- a first computation unit that iteratively computes messages for LDPC encoded information from check nodes to bit nodes, wherein the first computation unit computes at least some messages from a first one of the check nodes to one or more of the bit nodes and at least some messages from a second one of the check nodes to one or more of the bit nodes in block serial mode using shared hardware;
- and
- a second computation unit, responsive to the first computation unit, that iteratively computes messages for the LDPC encoded information from the bit nodes to the check nodes to produce a hard decoding decision.
A low density panty check (LDPC) decoding method comprising:
- iteratively computing messages for LDPC encoded information from check nodes to bit nodes, wherein at least some messages from a first one of the check nodes to one or more of the bit nodes and at least some messages from a second one of the check nodes to one or more of the bit nodes are computed in block serial mode using shared hardware in a first computation unit;
- and
- responsive to the first computation unit, iteratively computing messages for the LDPC encoded information from the bit nodes to the check nodes to produce a hard decoding decision in a second computation unit.
A wireless communication device comprising:
- a radio circuit that receives radio frequency signals;
- a modem that demodulates the received signals, wherein the signals are encoded with low density parity check (LDPC) codes;
- and
- an LDPC decoder including:
- a first computation unit that iteratively computes messages for LDPC encoded information from check nodes to bit nodes based on an approximation of the LDPC message passing algorithm, wherein the first computation unit computes at least some messages from a first one of the check nodes to one or more of the bit nodes and at least some messages from a second one of the check nodes to one or more of the bit nodes in block serial mode using shared hardware;
- and
- a second computation unit, responsive to the first computation unit, that iteratively computes messages for the LDPC encoded information from the bit nodes to the check nodes to produce a hard decoding decision.
4 more elements
A wireless communication device comprising:
- a radio circuit that receives radio frequency signals;
- a modern that demodulates the received signals, wherein the signals are encoded with low density parity check (LDPC) codes;
- and
- a low density parity check (LDPC) decoder including:
- a first computation unit that iteratively computes messages for LDPC encoded information from check nodes to bit nodes, wherein the first computation unit computes at least some messages from a first one of the check nodes to one or more of the bit nodes and at least some messages from a second one of the check nodes to one or more of the bit nodes in block serial mode using shared hardware;
- and
- a second computation unit, responsive to the first computation unit, that iteratively computes messages for the LDPC encoded information from the bit nodes to the check nodes to produce a hard decoding decision.
4 more elements
A low density parity check (LDPC) decoder comprising:
- a first computation unit that iteratively computes messages for LDPC encoded information from check nodes to bit nodes, wherein the first computation unit computes at least some messages from a first one of the check nodes to one or more of the bit nodes and at least some messages from a second one of the check nodes to one or more of the bit nodes in block serial mode using shared hardware;
- and
- a second computation unit that iteratively computes messages for the LDPC encoded information from the bit nodes to the check nodes.
A low density parity check (LDPC) decoding method comprising:
- iteratively computing messages for LDPC encoded information from check nodes to bit nodes, wherein at least some messages from a first one of the check nodes to one or more of the bit nodes and at least some messages from a second one of the check nodes to one or more of the bit nodes are computed in block serial mode using shared hardware in a first computation unit;
- and
- iteratively computing messages for the LDPC encoded information from the bit nodes to the check nodes in a second computation unit.
Dependencies are inferred from the claim text.