# US 2008/0189234 A1 · Search circuit in decoding unit of low-density parity-check codes and method thereof

> Agents: this data is available as JSON from the patentgrep API and MCP server — see https://patentgrep.com/llms.txt

- Number: US 2008/0189234 A1
- Document ID: US20080189234A1
- Status: Published application
- Kind: A1
- Application number: 12/022,449
- Filed: 2008-01-30
- Published: 2008-08-07
- Earliest claimed: 2007-02-01
- Assignees: Realtek Semiconductor Corp.
- Inventors: Chih-Yung Shih
- Web page: https://patentgrep.com/patent/US20080189234A1

## CPC

- G06F 7/22: Arrangements for sorting or merging computer data on continuous record carriers, e.g. tape, drum, disc
- H03M 13/1117: {using approximations for check node processing, e.g. an outgoing message is depending on the signs and the minimum over the magnitudes of all incoming messages according to the min-sum rule}
- H03M 13/112: {with correction functions for the min-sum rule, e.g. using an offset or a scaling factor}
- H03M 13/1122: {storing only the first and second minimum values per check node}
- H03M 13/658: {Scaling by multiplication or division}
- H03M 13/6583: {Normalization other than scaling, e.g. by subtraction}
- G06F: ELECTRIC DIGITAL DATA PROCESSING (computer systems based on specific computational models G06N)
- H03M: CODING; DECODING; CODE CONVERSION IN GENERAL (using fluidic means F15C4/00; optical analogue/digital converters G02F7/00; coding, decoding or code conversion, specially adapted for particular applications, see the relevant subclasses, e.g. G01D, G01R, G06F, G06T, G09G, G10L, G11B, G11C, H04B, H04L, H04M, H04N; ciphering or deciphering for cryptography or other purposes involving the need for secrecy G09C)

## Abstract

The present invention relates to a search circuit in a decoding unit of low-density parity-check codes, which used for searching a minimum value and a next minimum value from r input values, where r is an integer greater than 3. The search circuit includes a first search circuit and a second search circuit. The search method includes performing operations on each pair of input values Vi, Vj of the r input values, respectively. The second search circuit, which is coupled to the first search circuit, performs operations on every two sets of compared values Wm, Lm, and Wn, Ln of the s compared values, where s is a positive integer smaller than r, the smaller value Wm is smaller than the greater value Lm, and the smaller value Wn is smaller than the greater value Ln. The second search circuit performs operations according to the smaller value Wo and the greater value Lo to produce the minimum value and the next minimum value. Thereby, the search of the minimum value, the next minimum value, and the address of the minimum value can be performed at the same time without the need of waiting completion of search for the minimum value then the next minimum vale can be searched.

## Claims

### Claim 1

A search method, used for searching a minimum value and a next minimum value from r input values, where r is an integer greater than 3, comprising:
performing operations on two input values V1, V2 of the r input values, comprising:
comparing the two input values V1 and V2;
determining the input value V1 as a smaller value Wm and the input value V2 as a greater value Lm, if the input value V1 is smaller than the input value V2; and
determining the input value V2 as the smaller value Wm and the input value V1 as the greater value Lm, if the input value V2 is smaller than the input value V1;
performing operations on two input values V3, V4 of the r input values, comprising:
comparing the two input values V3 and V4;
determining the input value V3 as a smaller value Wn and the input value V4 as a greater value Ln, if the input value V3 is smaller than the input value V4; and
determining the input value V4 as the smaller value Wn and the input value V3 as the greater value Ln, if the input value V4 is smaller than the input value V3;
performing operations according to the smaller value Wm, the smaller value Wn, the greater value Lm, and the greater value Ln, comprising:
comparing the two smaller values Wm and Wn;
executing the following steps if the smaller value Wm is smaller than the smaller value Wn:
determining the smaller value Wm as a smaller value Wo; and
comparing the greater value Lm and the smaller value Wn, and determining the smaller of the two as a greater value Lo smaller than the smaller value Wm; and
executing the following steps if the smaller value Wn is smaller than the smaller value Wm:
determining the smaller value Wn as the smaller value Wo; and
comparing the greater value Ln and the smaller value Wm, and determining the smaller of the two as the greater value Lo smaller than the smaller value Wn; and
producing the minimum value and the next minimum value according to the smaller value Wo and the greater value Lo.

### Claim 2 (depends on 1)

The method of claim 1, and further comprising:
determining the corresponding address Pm of the smaller value Wm in the r input values as an address Po of the smaller value, if the smaller value Wm is smaller than the smaller value Wn; and
determining the corresponding address Pn of the smaller value Wn in the r input values as the address Po of the smaller value, if the smaller value Wn is smaller than the smaller value Wm.

### Claim 3

A search circuit, used for searching a minimum value and a next minimum value from r input values, where r is an integer greater than 3, comprising:
a first search circuit, used for performing operations on each pair of input values Vi, Vj of the r input values, respectively, comprising:
a first comparator, used for comparing if the input value Vi is smaller than the input value Vj, and for producing a first comparison signal; and
a first multiplexing circuit, used for outputting a set of compared valued according to the first comparison signal, outputting the smaller of the input value Vi and the input value Vj as the smaller value of the set of compared values, and outputting the greater of the Vi and Vj as the greater value of the set of compared values according to the first comparison signal;
a second search circuit, coupled to the first search circuit, used for performing operations on every two sets of compared values Wm, Lm, and Wn, Ln of the s compared values, where s is a positive integer smaller than r, the smaller value Wm being smaller than the greater value Lm, the smaller value Wn being smaller than the greater value Ln, and comprising:
a second comparator, used for comparing if the smaller value Wm is smaller than the smaller value Wn, and for producing a second comparison signal;
a second multiplexing circuit, used for outputting the smaller of the smaller value Wm and the smaller value Wn as a smaller value Wo according to the second comparison signal;
a third multiplexing circuit, used for outputting a set of compared values Wp, Wq according to the second comparison signal, outputting the smaller value Wn and the greater value Lm as the set of compared values Wp, Wq when the second comparison signal represents that the smaller value Wm is smaller than the smaller value Wn, and outputting the smaller value Wm and the greater value Ln as the set of compared values Wp, Wq when the second comparison signal represents that the smaller value Wn is smaller than the smaller value Wm;
a third comparator, used for comparing if the compared value Wp is smaller than the compared value Wq and for producing a third comparison signal; and
a fourth multiplexing circuit, used for outputting the smaller of the compared value Wp and the compared value Wq as a greater value Lo according to the third comparison signal;
wherein the second search circuit produces the minimum value and the next minimum value according to the smaller value Wo and the greater value Lo.

### Claim 4 (depends on 3)

The search circuit of claim 3, wherein the first multiplexing circuit includes:
a first multiplexing unit, used for outputting the smaller of the input value Vi and the input value Vj according to the first comparison signal; and
a second multiplexing unit, used for outputting the greater of the input value Vi and the input value Vj according to the first comparison signal.

### Claim 5 (depends on 3)

The search circuit of claim 3, wherein the corresponding address of the input value Vi in the r input values is Pi, the corresponding address of the input value Vj in the r input values is Pj, and the first multiplexing circuit further outputting the corresponding address Pi or Pj of the smaller of the input value Vi and the input value Vj to the second search circuit according to the first comparison signal.

### Claim 6 (depends on 5)

The search circuit of claim 5, wherein the first multiplexing circuit further comprising a third multiplexing unit, outputting the corresponding address Pi or Pj of the smaller of the input value Vi and the input value Vj to the second search circuit according to the first comparison signal.

### Claim 7 (depends on 6)

The search circuit of claim 6, wherein the corresponding address of the smaller value Wm is Pm, the corresponding address of the smaller value Wn is Pn, and the second multiplexing circuit further outputting the corresponding address Pm or Pn of the smaller of the smaller value Wm and the smaller value Wn according to the second comparison signal.

### Claim 8 (depends on 7)

The search circuit of claim 7, wherein the second multiplexing circuit includes:
a fourth multiplexing unit, used for outputting the smaller of the smaller value Wm and the smaller value Wn according to the second comparison signal; and
a fifth multiplexing unit, used for outputting the corresponding address Pm or Pn of the smaller of the smaller value Wm and the smaller value Wn according to the second comparison signal.

### Claim 9 (depends on 3)

The search circuit of claim 3, wherein the third multiplexing circuit includes:
a sixth multiplexing unit, used for receiving the second comparison signal, the smaller value Wm, and the greater value Lm, outputting the greater value Lm when the second comparison signal represents that the smaller value Wm is smaller than the smaller value Wn, and outputting the smaller value Wm when the second comparison signal represents that the smaller value Wn is smaller than the smaller value Wm; and
a seventh multiplexing unit, used for receiving the second comparison signal, the smaller value Wn, and the greater value Ln, outputting the smaller value Wn when the second comparison signal represents that the smaller value Wm is smaller than the smaller value Wn, and outputting the greater value Ln when the second comparison signal represents that the smaller value Wn is smaller than the smaller value Wm.

### Claim 10

A search circuit, used for searching a minimum value and a next minimum value from r input values, where r is an integer greater than 3, comprising:
a first search circuit, used for performing operations on each pair of input values Vi, Vj of the r input values, respectively, comprising:
a first comparator, used for comparing if the input value Vi is smaller than the input value Vj, and for producing a first comparison signal; and
a first multiplexing circuit, used for outputting a set of compared valued according to the first comparison signal, outputting the smaller of the input value Vi and the input value Vj as the smaller value of the set of compared values, and outputting the greater of the Vi and Vj as the greater value of the set of compared values according to the first comparison signal; and
a second search circuit, coupled to the first search circuit, used for performing operations on every two sets of compared values Wm, Lm, and Wn, Ln of the s compared values, where s is a positive integer smaller than r, the smaller value Wm being smaller than the greater value Lm, the smaller value Wn being smaller than the greater value Ln, and comprising:
a second comparator, used for comparing if the smaller value Wm is smaller than the smaller value Wn, and for producing a second comparison signal;
a second multiplexing circuit, used for outputting the smaller of the smaller value Wm and the smaller value Wn as a smaller value Wo according to the second comparison signal;
a third comparator, used for comparing if the greater value Lm is smaller than the smaller value Wn and for producing a third comparison signal;
a third multiplexing circuit, used for outputting the smaller of the greater value Lm and the smaller value Wn as a smaller value Wr;
a fourth comparator, used for comparing if the smaller value is smaller than the greater value Ln and for producing a fourth comparison signal; and
a fourth multiplexing circuit, used for outputting the smaller of the smaller value Wm and the greater value Ln as a smaller value Wz according to the fourth comparison signal;
wherein the second multiplexing circuit further outputs the smaller of the smaller value Wr and the smaller value Wz as a greater value Lo according to the second comparison signal, and the second search circuit produces the minimum value and the next minimum value according to the smaller value Wo and the greater value Lo.

### Claim 11 (depends on 10)

The search circuit of claim 10, wherein the first multiplexing circuit includes:
a first multiplexing unit, used for outputting the smaller of the input value Vi and the input value Vj according to the first comparison signal; and
a second multiplexing unit, used for outputting the greater of the input value Vi and the input value Vj according to the first comparison signal.

### Claim 12 (depends on 10)

The search circuit of claim 10, wherein the corresponding address of the input value Vi in the r input values is Pi, the corresponding address of the input value Vj in the r input values is Pj, and the first multiplexing circuit further outputting the corresponding address Pi or Pj of the smaller of the input value Vi and the input value Vj to the second search circuit according to the first comparison signal.

### Claim 13 (depends on 12)

The search circuit of claim 12, wherein the first multiplexing circuit further comprising a third multiplexing unit, outputting the corresponding address Pi or Pj of the smaller of the input value Vi and the input value Vj to the second search circuit according to the first comparison signal.

### Claim 14 (depends on 12)

The search circuit of claim 12, wherein the corresponding address of the smaller value Wm is Pm, the corresponding address of the smaller value Wn is Pn, and the second multiplexing circuit further outputting the corresponding address Pm or Pn of the smaller of the smaller value Wm and the smaller value Wn according to the second comparison signal.

### Claim 15 (depends on 14)

The search circuit of claim 14, wherein the second multiplexing circuit includes:
a fourth multiplexing unit, used for outputting the smaller of the smaller value Wm and the smaller value Wn as the smaller value Wo according to the second comparison signal;
a fifth multiplexing unit, used for outputting the smaller of the smaller value Wr and the smaller value Wz as the greater value Lo according to the second comparison signal;
a sixth multiplexing unit, used for outputting the corresponding address Pm or Pn of the smaller of the smaller value Wm and the smaller value Wn according to the second comparison signal.

### Claim 16 (depends on 10)

The search circuit of claim 10, wherein the second multiplexing circuit includes:
a fourth multiplexing unit, used for outputting the smaller of the smaller value Wm and the smaller value Wn as the smaller value Wo according to the second comparison signal; and
a fifth multiplexing unit, used for outputting the smaller of the smaller value Wr and the smaller value Wz as the greater value Lo according to the second comparison signal.
