JP7110191B2 - Information processing device and method - Google Patents

Description

TECHNICAL FIELD The present disclosure relates to an information processing apparatus and method, and more particularly to an information processing apparatus and method capable of suppressing an increase in circuit size.

Conventionally, in terrestrial digital broadcasting, a difference cyclic code has been used as an error correction method for control signal transmission, and BP (Belief Propagation) decoding has been used as a decoding method for the difference cyclic code. BP decoding has higher error correction capability than other decoding methods such as majority decoding and APP (A Posterior Probability) soft decision decoding.

JP 2010-199920 A

However, in the case of BP decoding, since access to memory elements that hold intermediate information used for decoding becomes complicated, there is a risk of an increase in circuit size, such as an increase in the number of wirings to the memory elements.

The present disclosure has been made in view of such circumstances, and is intended to suppress an increase in the circuit scale of decoding related to error correction.

An information processing device according to one aspect of the present technology stores a plurality of pieces of information used for decoding in different regions, and shifts the region for storing the information to correspond to the shift in the column direction of the parity check matrix for the decoding. a storage unit that shifts according to the computation of the parity check matrix, reading the information from a predetermined area of the storage unit, and arranging the information updated by the computation related to the decoding so as to correspond to the shift in the row direction of the parity check matrix and an update unit that writes data to a predetermined area of the storage unit instead, and an operation unit that performs operations related to the decoding using the information read from the storage unit by the update unit, and updates the information. processing equipment.

An information processing method according to one aspect of the present technology stores a plurality of pieces of information used for decoding in different regions of a storage unit, and stores the information in regions corresponding to the shift in the column direction of the parity check matrix for the decoding. is shifted in accordance with the computation related to the decoding, the information is read from a predetermined area of the storage unit, the computation related to the decoding is performed using the information read from the storage unit, and the information is updated; In the information processing method, the updated information is rearranged so as to correspond to the shift in the row direction of the parity check matrix, and the information is written in a predetermined area of the storage unit.

In the information processing device and method of one aspect of the present technology, a plurality of pieces of information used for decoding are stored in mutually different regions of the storage unit, and the pieces of information are stored so as to correspond to the shift in the column direction of the parity check matrix for the decoding. The area to be stored is shifted in accordance with the computation related to decoding, the information is read from a predetermined area of the storage section, and the information read out from the storage section is used to perform the computation related to decoding and update the information. The updated information is rearranged so as to correspond to the shift in the row direction of the parity check matrix, and written in a predetermined area of the storage unit.

According to the present disclosure, information can be processed. In particular, it is possible to suppress an increase in circuit scale for decoding related to error correction.

It is a figure which shows the main structural examples of a majority decoding circuit. FIG. 4 is a diagram showing a main configuration example of an APP soft-decision decoding circuit; 2 is a block diagram showing a main configuration example of a BP decoding device; FIG. FIG. 4 is a diagram explaining an example of a BP decoding algorithm; FIG. 4 is a diagram explaining an example of a BP decoding algorithm; It is a figure explaining a processing order. FIG. 10 is a diagram for explaining cyclic shift in the column direction; FIG. 4 is a diagram for explaining readout positions for each column; FIG. 10 is a diagram illustrating an example of the relationship between cyclic shift in the matrix direction and readout positions; 2 is a block diagram showing a main configuration example of a BP decoding device; FIG. FIG. 3 is a diagram showing a main configuration example of a shift buffer and a computing unit; FIG. 4 is a diagram illustrating an example of parity check matrix and readout positions; FIG. 11 is a flowchart for explaining an example of the flow of BP decoding processing; FIG. FIG. 5 is a diagram showing an example of the relationship between signal-to-noise ratio and error rate; FIG. 10 is a diagram explaining an example of a shuffled BP decoding algorithm; FIG. 10 is a diagram showing a main configuration example of a shift buffer and a calculation unit when Shuffled BP decoding is performed; It is a figure explaining the example of check node operation. It is a figure explaining the example of check node operation. It is a block diagram which shows the main structural examples of a receiver. It is a block diagram which shows an example of a schematic structure of a television apparatus. It is a block diagram which shows the main structural examples of a computer.

Hereinafter, a form for carrying out the present disclosure (hereinafter referred to as an embodiment) will be described. The description will be given in the following order.
1. Decoding method of cyclic code2. First embodiment (BP decoding device)
3. Second Embodiment (Shuffled BP)
4. Third Embodiment (Check Node Operation)
5. Fourth embodiment (receiving device)
6. Fifth Embodiment (Television Device)
7. others

<1. Decoding Method of Cyclic Code>
<Decryption method example>
Conventionally, a difference-set cyclic code is used as an error correction method for control signal transmission in digital terrestrial broadcasting.

In the set of J non-negative integers less than or equal to J(J-1) for a positive integer J, all the ordered differences modulo n=J(J-1)+1 of any two elements Different ones are called simple complete difference sets of order J modulo n. Let {d1,d2,...,dJ} be the simple complete difference set of order J modulo n, then D(x) = x^{d1} + x^{d2} + … + x^{ dJ} as a code polynomial, and the binary cyclic code with the minimum number of codewords is assumed to be C _D . This C _D dual code is called a difference set cyclic code.

Various studies have been made on decoding methods and apparatus for such difference-set cyclic codes. For example, majority decoding, variable threshold decoding, bit-flipping decoding, etc. have been studied as hard-decision decoding methods. As soft-decision decoding methods, APP (A Posterior Probability) soft-decision decoding, variable threshold soft-decision decoding, BP (Belief Propagation) decoding, etc. have been studied.

An example of a conventional decoding scheme will be described below. Note that the difference set cyclic code will be described with a code length N=7 and an information length k=3. The complete simple difference set in this case is {0,1,3} and J=3.

<Majority decoding>
FIG. 1 is a diagram showing a main configuration example of a majority decoding circuit. As shown in FIG. 1A, the majority decoding circuit 10 that performs majority decoding includes delay elements 11-1 to 11-7, arithmetic units 12-1 to 12-3, a majority decision unit 13, and , and a computing unit 14 .

Each of the delay elements 11-1 to 11-7 holds the signal for a predetermined period and delays the output timing with respect to the input timing. qi (i = 0 to 6) on each delay element indicates the signal held in that delay element. Since majority decoding is hard decision decoding, this signal qi is a 1-bit signal. That is, each of the delay elements 11-1 to 11-7 is a 1-bit delay element. The delay elements 11-1 through 11-7 are connected in a loop, and the signal is cyclically shifted through the delay elements 11-1 through 11-7 (delay elements 11-1 through 11-7). -7, and after the delay element 11-7, it is returned to the delay element 11-1 and held). The signal output from the delay element 11-7 is also supplied to the computing section 14. FIG.

The arithmetic units 12-1 to 12-3 and the arithmetic unit 14, as shown in FIG. 1B, perform an exclusive OR operation (EXOR) of multiple inputs and output the operation result. The calculation unit 12-1 obtains the exclusive OR of the output (q1) of the delay element 11-2, the output (q2) of the delay element 11-3, and the output (q6) of the delay element 11-7, and calculates The result is supplied to the majority decision section 13 . The calculation unit 12-2 obtains the exclusive OR of the output (q0) of the delay element 11-1, the output (q4) of the delay element 11-5, and the output (q6) of the delay element 11-7, and calculates The result is supplied to the majority decision section 13 . The calculation unit 12-3 obtains the exclusive OR of the output (q3) of the delay element 11-4, the output (q5) of the delay element 11-6, and the output (q6) of the delay element 11-7, and calculates The result is supplied to the majority decision section 13 . The calculation unit 14 obtains the exclusive OR of the output (q6) of the delay element 11-7 and the output (majority result) of the majority determination unit 13, and outputs the calculation result to the outside of the majority decoding circuit 10. FIG.

The majority determination unit 13 determines the majority of the computation results of the computation units 12-1 to 12-3 and supplies the determination result to the computation unit 14. FIG.

The majority decoding circuit 10 having such a configuration sets the received hard decision information (1 bit) in each delay element (delay element 11-1 to delay element 11-7) as initialization. Next, as a decoding process, the arithmetic units 12-1 to 12-3 each perform an exclusive OR operation on the signal qi, and the majority decision unit 13 performs an exclusive OR operation result (EXOR result) to decide whether or not to correct the signal. Next, the majority decoding circuit 10 cyclically shifts the values of the delay elements 11-1 to 11-7 as cyclic shift processing. The majority decoding circuit 10 repeats such decoding processing and cyclic shift processing N times.

If there is no error in the signal, the outputs of the calculation units 12-1 through 12-3 are "0". If there is an error in the signal, the outputs of the calculation units 12-1 to 12-3 are "1". The majority determination unit 13 aggregates the outputs of the calculation units 12-1 to 12-3, and determines that the signal value is erroneous when there are many "1"s. In that case, the calculator 14 corrects the value of the signal.

<APP soft decision decoding>
FIG. 2 is a diagram showing a main configuration example of the APP soft-decision decoding circuit. As shown in A of FIG. 2, the APP soft-decision decoding circuit 20 that performs APP soft-decision decoding includes delay elements 21-1 to 21-7, calculation units 22-1 to 22-3, calculation units 23 and a determination unit 24 .

Each of the delay elements 21-1 to 21-7 holds the signal for a predetermined period and delays the output timing with respect to the input timing. ri (i = 0 to 6) on each delay element indicates a soft-decision LLR (log likelihood ratio) of s (>1) bits or more held in that delay element. That is, each of the delay elements 21-1 through 21-7 is an s (>1) bit delay element. The delay elements 21-1 through 21-7 are connected in a loop, and the soft-decision LLR cyclically shifts the delay elements 21-1 through 21-7 (delay element 21-1 through delay element 21-7). are held in order by the element 21-7, and after the delay element 21-7 are returned to and held by the delay element 21-1).

The calculation units 22-1 to 22-3 each perform calculation (LLR calculation) as shown at the top of B in FIG. 2, and output the calculation result. The calculation section 22-1 performs LLR calculation using the output (r1) of the delay element 21-2 and the output (r2) of the delay element 21-3, and supplies the calculation result to the calculation section . The calculation section 22-2 performs LLR calculation using the output (r0) of the delay element 21-1 and the output (r4) of the delay element 21-5, and supplies the calculation result to the calculation section . The calculation section 22-3 performs LLR calculation using the output (r3) of the delay element 21-4 and the output (r5) of the delay element 21-6, and supplies the calculation result to the calculation section .

The calculation unit 23, as shown second from the top of FIG. Find the sum. The calculation unit 23 supplies the sum to the determination unit 24 . The determination unit 24 determines an error based on the calculation result (sum) of the calculation unit 23, as shown at the bottom of B in FIG. For example, the determination unit 24 determines that there is no error when the calculation result (sum) of the calculation unit 23 is positive, and determines that there is an error when the calculation result is 0 or less. The decision section 24 outputs such a decision result to the outside of the APP soft decision decoding circuit 20 .

The APP soft-decision decoding circuit 20 having such a configuration sets the received soft-decision information (s bits) in each delay element (delay element 21-1 to delay element 21-7) as initialization. Next, as a decoding process, the calculation units 22-1 to 22-3 each perform LLR calculation using the soft decision information ri, and the calculation unit 23 uses the calculation results and the delay element 21-7 , and the determination unit 24 determines whether or not there is an error based on the sum. Next, the APP soft decision decoding circuit 20 cyclically shifts the values of the delay elements 21-1 through 21-7 as cyclic shift processing. The APP soft decision decoding circuit 20 repeats such decoding processing and cyclic shift processing N times.

As a loop configuration, instead of the output (r6) of the delay element 21-7, the output (λ) of the arithmetic unit 23 may be supplied to the delay element 21-1.

<BP decryption>
FIG. 3 is a diagram showing a main configuration example of the BP decoding device. As shown in FIG. 3, a BP decoding circuit 30 that performs BP decoding includes an address generation unit (address generator) 31, a control unit (controller) 32, a calculation unit (variable & check node calculator) 33, and a RAM ( Random Access Memory) 34 .

The computation unit 33 repeats check node computation for all rows of the parity check matrix and variable node computation for all columns multiple times. When performing check node calculation, the calculation unit 33 reads information corresponding to the position of the non-zero element (non-zero coefficient) in each row of the parity check matrix for the received information ri and the intermediate information vi,i from the RAM 34, and uses the read information to perform calculations. When performing variable node calculation, the calculation unit 33 reads information corresponding to the position of the non-zero element (non-zero coefficient) in each column of the parity check matrix for the intermediate information ui,i from the RAM 34, and performs calculation using the read information. I do.

That is, the read position of information (received information and intermediate information) changes depending on the position of the non-zero coefficients in the parity check matrix, so the RAM 34 is used to hold this information. The address generator 31 sets the information readout address according to the position of the non-zero coefficient in the parity check matrix. The control unit 32 controls reading from the RAM 34 based on the address information. As shown in FIG. 3, a plurality of memory cells (Memory Cells) are provided inside the RAM 34, and received information and intermediate information are stored in each memory cell. The control unit 32 controls reading and writing of information from/to each memory cell, thereby controlling from which memory cell the calculation unit 33 reads information and from which memory cell the calculation unit 33 writes information. to control.

An example of this BP decoding algorithm is shown in A of FIG. The computing unit 33 performs check node computation as shown in A of FIG. 4 for each row of the parity check matrix, and performs variable node computation as shown in A of FIG. 4 for each column of the parity check matrix. The parity check matrix is composed of elements (coefficients) with a value of 0 or 1 as shown in FIG. These operations are performed using the corresponding information.

<Characteristics of BP decoding>
Such BP decoding is soft-decision decoding, and has high error correction capability, such as being used for decoding LDPC (Low Density Parity Check) codes. However, in the case of BP decoding, the positions of non-zero coefficients in the parity check matrix change depending on the columns and rows, so the information used for decoding also changes accordingly. This complicates access to storage elements that hold information (increases variations in access destinations). As a result, the number of wirings to the storage elements increases, and there is a risk that wiring congestion will increase and the circuit scale will increase. For example, the selector connected to Read Data in FIG. 3 has a large scale. In addition, write data must be connected to each storage element, and there are many wires, and the more connections there are, the higher the drive capacity of the output source device, etc. Wiring congestion affects the circuit scale. I was afraid.

The number of addresses of the RAM 34 that can be accessed simultaneously depends on the specifications of the RAM 34, but there is a possibility that the circuit size will increase due to the increase in wiring required for simultaneous access to a plurality of addresses. In addition, since the RAM is used, the address generator 31 and the like are required, which may increase the circuit scale.

A method of holding information using a register instead of RAM is also conceivable, but even in that case, since the address from which the calculation unit 33 reads out information is variable, the address generation unit 31 is required and the circuit scale is increased. It was likely to increase. In addition, when the operation unit 33 performs either check node operation or variable node operation, if the information required for one operation is distributed and held at a plurality of addresses, access requires a plurality of cycles, resulting in a decoding delay. was likely to increase.

<2. First Embodiment>
<Application of cyclic shift memory element>
Therefore, a plurality of pieces of information used for decoding are stored in different areas of the storage unit, and the area for storing the information is shifted according to the computation related to decoding so as to correspond to the shift in the column direction of the parity check matrix for the decoding. , reads information from a predetermined area of the storage unit, performs arithmetic operations related to decoding using the information read from the storage unit, updates the information, and stores the updated information in the row direction of the parity check matrix. The data are rearranged so as to correspond to the shift, and written in a predetermined area of the storage unit.

In this way, by cyclically shifting the parity check matrix in the matrix direction for each calculation, the positions of the non-zero coefficients are fixed, so that information can be read from the same area of the storage unit. Therefore, it is possible to suppress an increase in the number of wirings connected to the storage unit for reading and writing information, and it is possible to suppress an increase in circuit size.

<BP decoding algorithm>
For this purpose, for example, the BP decoding algorithm is equivalently transformed as shown in FIG. In other words, the order of information update is changed in one repetition. Also, processing is performed in the order of the columns of the parity check matrix. Furthermore, check node operation and variable node operation are performed only at non-zero element positions (non-zero coefficient positions) in each column.

More specifically, as shown in FIG. 5, for information corresponding to the positions of non-zero coefficients in each column of the parity check matrix, a check node operation such as the following equation (1) and the following equation A variable node operation such as (2) and information calculation such as the following equation (3) are performed.

・・・（１）

・・・（２）

・・・（３）

... (1)

... (2)

... (3)

Also, the above calculation is performed for each column. Furthermore, after that, the information is updated as shown in the following formula (4).

・・・（４）

... (4)

FIG. 6 shows an example of a parity check matrix. As shown in FIG. 6, the loop for number of non-zero elements (0≦I<J) in the algorithm shown in FIG. 5 corresponds to the cyclic shift in the row direction of the parity check matrix, and the algorithm shown in FIG. A loop for number of columns (0≦j<N) corresponds to a cyclic shift in the column direction of the parity check matrix.

<BP calculation target position>
As shown in FIG. 7, from the nature of the difference-set cyclic code, intermediate information (A, B, C) is arranged at non-zero element positions of the parity check matrix and cyclically shifted to perform a node operation (check node). You can read the information necessary for calculations and variable node calculations). However, since no information is placed in the 0 element position, it is necessary to either put a wasteful buffer for the cyclic shift or control the cycle of the cyclic shift. Therefore, this method may increase the circuit scale.

Therefore, attention is focused on columns (columns surrounded by dotted lines) to be operated, such as the parity check matrix shown on the leftmost side of FIG. 8 . Since the node operation is performed using the information of the row that is the non-zero element position in the column direction (the row surrounded by the dotted line in the matrix shown second from the left (middle) in FIG. 8), As in the rightmost matrix, it is only necessary to buffer information on non-zero element positions in the row direction. The reading position can be limited by using the regularity of which row corresponds to the column to be operated.

For example, in the case of the top row matrix, since the rightmost column is targeted, the first, second, and fourth rows from the top where nonzero coefficients are present are targeted. Therefore, as shown in the rightmost part of FIG. The rightmost "C" of the eye is read.

Then, like the second row from the top, the second column from the right is targeted. Therefore, the 1st, 3rd, and 7th rows from the top where non-zero coefficients exist are targeted. That is, as shown in the rightmost part of FIG. The rightmost "A" in the row is read.

Then, the third column from the right is targeted, such as the third row from the top. Therefore, the 2nd, 6th, and 7th rows from the top where non-zero coefficients are present are targeted. That is, as shown in the rightmost part of FIG. The second "B" from the right in the row is read.

A more specific description will be given with reference to FIG. As shown in the top row of FIG. 9, the processing target of the variable node operation of BP decoding starts from the rightmost column of the parity check matrix, then the second column from the right, then The third column from the right, . . . are specified one by one in order from the right. The check node operation is performed on the nonzero coefficients in the same row as the nonzero coefficients in the target column of the variable node operation.

Therefore, as shown in the second row from the top (middle row) in FIG. 9, each coefficient of the parity check matrix is cyclically shifted in the column direction (the column order is changed as indicated by the arrow in the figure) each time the node operation is performed. ), the processing target of the variable node operation is fixed to the rightmost column of the parity check matrix.

Further, as shown in the bottom row of FIG. 9, each coefficient of the parity check matrix is cyclically shifted not only in the column direction but also in the row direction (as indicated by the arrows in the figure). If the row order is changed respectively), the positions of the coefficients to be processed by the check node computation as well as the variable node computations are fixed. In other words, it is possible to fix the area (address) from which the information used for the node calculation is read from the buffer.

Therefore, a large selector such as the selector connected to Read Data in FIG. 3 can be omitted. Also, the number of wirings for Write Data can be reduced. Therefore, an increase in wiring congestion can be suppressed. Also, for example, the address generator can be omitted. As described above, an increase in circuit scale can be suppressed. The same is true when using registers instead of RAM.

<BP decoding device>
FIG. 10 is a block diagram showing a main configuration example of a BP decoding device, which is an embodiment of an information processing device to which the present technology is applied. The BP decoding device 200 shown in FIG. 10 BP-decodes a difference-set cyclic code such as an LDPC code. As shown in FIG. 10, the BP decoding device 200 has shift buffers 211 (Shift buffers), a calculator 212 (variable & check node calculator), and an iteration controller 213 (iteration control circuit).

The shift buffer 211 has a cyclic shift buffer for storing received information r and a cyclic shift buffer for storing intermediate information zi,j. A cyclic shift buffer is a buffer that cyclically shifts an area (buffer) for storing information.

A cyclic shift buffer that stores the received information r is composed of, for example, a plurality of buffer cells 222 connected in a loop. This circular shift buffer can store received information r in each buffer cell 222 . Also, this cyclic shift buffer can move the received information r stored in each buffer cell 222 to the next buffer cell 222 (in the example of FIG. 10, the buffer cell 222 on the right). At this time, the output of the buffer cell 222 on the right end of the drawing is supplied to the buffer cell 222 on the left end of the drawing. That is, this cyclic shift buffer can cyclically shift the received information r (update the area storing the received information r) along the loop of the buffer cells 222 having such a configuration. For example, this cyclic shift buffer cyclically shifts the received information r corresponding to a node operation (for example, each time a node operation is performed).

In FIG. 10, only the leftmost buffer cell is labeled, but all the buffer cells arranged horizontally in the drawing are the buffer cells 222 . A selection unit 221 is provided on the input side of the buffer cell 222 on the left end of the drawing, and the reception information r supplied from the outside or the reception information r supplied from the buffer cell 222 on the right end of the drawing is It is designed to be supplied to the leftmost buffer cell 222 .

A cyclic shift buffer that stores the intermediate information zi,j is composed of, for example, a plurality of buffer cells 223 connected in a loop. This circular shift buffer can store intermediate information zi,j in each buffer cell 223 . Also, this cyclic shift buffer can move the intermediate information zi,j stored in each buffer cell 223 to the next buffer cell 223 (in the example of FIG. 10, the buffer cell 223 on the right). At this time, the output of the buffer cell 223 on the right end of the figure is supplied to the buffer cell 223 on the left end of the figure. In other words, this cyclic shift buffer can cyclically shift the intermediate information zi,j (update the area storing the intermediate information zi,j) along the loop of the buffer cells 223 having such a configuration. . For example, this cyclic shift buffer cyclically shifts the intermediate information zi,j corresponding to a node operation (for example, each time a node operation is performed).

In FIG. 10, only the leftmost buffer cell is labeled, but all the buffer cells arranged in the horizontal direction in the drawing are buffer cells 223 . The number of buffer cells 223 in the cyclic shift buffer storing the intermediate information zi,j is the same as the number of buffer cells 222 in the cyclic shift buffer storing the received information r.

Furthermore, the output of some buffer cells 223 of the cyclic shift buffer that stores the intermediate information zi,j is connected to the next buffer cell 223 via the arithmetic section 212 . For example, it is wired so that the output of the buffer cell 223 at a predetermined position of this cyclic shift buffer is supplied to the arithmetic unit 212 . In other words, the arithmetic unit 212 reads out the intermediate information zi,j from the buffer cell 223 at a predetermined position of the cyclic shift buffer.

Further, for example, the calculation result (updated intermediate information zi,j) obtained by the calculation unit 212 is stored in the buffer cell 223 (FIG. 10, it is wired to be supplied to the adjacent buffer cell 223) on the right. The connection position through the arithmetic unit 212 is uniquely determined by the code configuration.

The calculation unit 212 performs check node calculation and variable node calculation for BP decoding, and outputs the decoding result.

The repetition control unit 213 performs initialization when receiving information is input and controls the number of repetitions. At the time of initialization, the cyclic shift buffer of the intermediate information zi,j is set to 0, and read/write buffer control is performed depending on whether the number of iterations is even or odd.

FIG. 11 is a diagram showing a main configuration example of the shift buffer 211 and the arithmetic unit 212. As shown in FIG. As described above, the shift buffer 211 has the selector 221, a cyclic shift buffer in which a plurality of buffer cells 222 are connected in a loop, and a cyclic shift buffer in which a plurality of buffer cells 223 are connected in a loop. .

The calculation unit 212 has a configuration as an update unit that reads information from a predetermined buffer cell of the shift buffer 211 and writes the updated information in a predetermined area of the shift buffer 211, and a node calculation unit that performs node calculations related to BP decoding. It has a configuration as

The calculation unit 212 includes selection units 231-1 to 231-3, buffers 232-1 to 232-3, a selection unit 233, buffers 234-1 to 234-3, and selection units 231-1 to 231-3. It has a portion 235 (the configuration shown above the dotted line 241 in the drawing). In addition, the operation unit 212 includes check node operation units 236-1 to 236-3 (the configuration shown between the dotted lines 241 and 242 in the drawing) and a variable node operation unit as the configuration of the node operation unit. section 237 (structure shown between dotted line 242 and dotted line 243 in the drawing), information updating sections 238-1 to 238-3 (structure shown below dotted line 243 in the drawing), and determination section 239.

Note that the selection units 231-1 to 231-3 are referred to as the selection unit 231 when there is no need to distinguish them from each other. Also, the buffers 232-1 to 232-3 are referred to as the buffer 232 when there is no need to distinguish them from each other. The buffers 234-1 through 234-3 are referred to as buffers 234 when there is no need to distinguish them from each other. The check node computing units 236-1 to 236-3 are referred to as check node computing units 236 when there is no need to distinguish them from each other. The information updating units 238-1 to 238-3 are referred to as the information updating unit 238 when there is no need to distinguish them from each other.

In FIG. 11, only the selection section 233 on the rightmost side of the drawing is denoted by a reference numeral. Similarly, only the selection section 235 on the rightmost side of the figure is denoted by a reference numeral, but the selection section 235 and the selection sections aligned horizontally in the figure are all referred to as the selection section 235 .

The selection unit 231 selects either the value of the buffer 232 corresponding to itself or the initial value (for example, “0”) according to the value of the control signal “reciving data” supplied from the repetition control unit 213 . It selects and supplies the selected value to a buffer cell 223 at a predetermined position (the buffer cell 223 next to the buffer cell 223 from which the information is read) of the cyclic shift buffer of the intermediate information zi,j for storage.

The buffer 232 stores the intermediate information zi,j to be written into (the buffer cell 223 of) the cyclic shift buffer of the intermediate information zi,j.

According to the value of the control signal “even/odd” supplied from the repetition control unit 213, the selection unit 233 selects the value of the buffer 234 corresponding to itself and the updated value supplied from the information update unit 238 corresponding to itself. It selects one of the intermediate information zi,j and supplies the selected value to its corresponding buffer 232 .

The buffer 234 acquires and stores the value of the buffer cell 223 at a predetermined position in the cyclic shift buffer of the intermediate information zi,j. Further, the buffer 234 supplies the stored value to the buffer 232 corresponding to itself, the selection unit 233 corresponding to itself, or the selection unit 235 corresponding to itself.

The selection unit 235 selects one of a plurality of values of the buffer 234 corresponding to itself according to the value of the control signal “even/odd” supplied from the repetition control unit 213, and transfers the selected value to itself. It is supplied to the corresponding check node calculation unit 236 .

The check node computation unit 236 uses the supplied intermediate information zi,j to perform check node computation such as the following equation (5), for example.

・・・（５）

... (5)

Also, the check node calculation unit 236 supplies the calculated value to the variable node calculation unit 237 and the information update unit 238 corresponding thereto.

The variable node computation unit 237 uses the supplied check node computation result to perform variable node computation such as the following equation (6), for example.

・・・（６）

... (6)

Also, the variable node calculation unit 237 supplies the calculated values to each information update unit 238 and the determination unit 239 .

The information update unit 238 uses the supplied check node calculation result and variable node calculation result to perform calculation for information update, such as the following equation (7).

・・・（７）

... (7)

Also, the information updating unit 238 supplies the obtained calculation result (the updated intermediate information zi,j) to the selecting unit 233 corresponding to itself.

The determination unit 239 performs error determination based on the supplied variable node calculation result. For example, if the variable node calculation result is a positive value, it is determined that there is no error, and if the variable node calculation result is 0 or less, it is determined that there is an error. The determination section 239 outputs the determination result to the outside of the BP decoding section.

These configurations correspond to the configuration of the parity check matrix used for BP decoding (positions of non-zero coefficients thereof). That is, the configuration shown in FIG. 11 is an example. The configurations of shift buffer 211 and computing section 212 are not limited to the example in FIG. 11 as long as they correspond to the configuration of the parity check matrix used for BP decoding. For example, the configuration example in FIG. 11 corresponds to the parity check matrix shown in FIG.

In the BP decoding device 200 having such a configuration, at the time of initialization, the received signal r is supplied to and stored in a cyclic shift buffer (buffer cell 222) that stores received information. Further, the selector 231 is controlled to supply the value "0" to the cyclic shift buffer (buffer cell 223) that stores the intermediate information zi,j to store it. That is, the intermediate information zi,j is set to "0". By repeating the above processing for N cycles, recording of received information and zero initialization are completed.

In BP decoding, intermediate information is calculated by check node operation and variable node operation, and the information is used in the next iteration. The cyclic shift buffer that holds the intermediate information is used by switching between the read side and the write side depending on whether it is repeated even-numbered times or odd-numbered times. Cyclic shift of the intermediate information zi,j in the column direction uses a cyclic shift buffer consisting of N buffer cells 223 holding J×2 pieces of information. For example, in the case of FIG. 11, the cyclic shift buffer holding intermediate information is composed of seven buffer cells 223 connected in a loop.

The shift buffer 211 cyclically shifts the intermediate information zi,j so as to correspond to the shift in the column direction of the parity check matrix, corresponding to the node operation (every node operation). As a result, among the cyclic shifts in the matrix direction described above with reference to FIG. 9, cyclic shifts in the column direction can be realized.

Also, the update unit of the calculation unit 212 uses the buffers 232 and 234 to rearrange the intermediate information zi,j updated by the node calculation so as to correspond to the shift in the row direction of the parity check matrix. Thereby, among the cyclic shifts in the matrix direction described above with reference to FIG. 9, cyclic shifts in the row direction can be realized.

That is, with the above configuration, the BP decoding device 200 can complete BP decoding by repeating the cyclic shift of data using the regularity of the difference set cyclic code. Therefore, the number of cycles required for one iteration is N, and if the number of iterations is lmax, decoding is completed in N×lmax cycles.

Note that processing such as check node calculation, variable node calculation, information update, and determination for obtaining a decoding result by the calculation unit 212 are performed in the same manner as in normal BP decoding. Although the parity check circuit is omitted in the example of FIG. 11, it can be easily implemented by recording the decoded result in the shift buffer like other information.

In addition, in the calculation unit 212, the configuration of the updating unit and the node calculation unit has a number depending on the column weight (the number of non-zero elements in the column direction) of the parity check matrix. For example, for column weight J, the calculator 212 has J updaters and node calculators. In the example of FIG. 11, the number of non-zero elements in the column direction of the parity check matrix is 3 as shown in FIG. , are provided three by one.

Note that it may be less than J when circuit resources are shared for scale reduction. However, the shift timing of the cyclic shift buffer must be synchronized with the operation cycle.

Also, the connection position between the cyclic shift buffer of the shift buffer 211 and the update unit of the calculation unit 212 corresponds to the non-zero element position in the column direction of the parity check matrix. In the example of FIG. 11, the non-zero element positions in the rightmost column of the parity check matrix are the first, second, and fourth from the top, so the first buffer from the right (seventh from the left) in FIG. The intermediate information zi,j is read out from the cell 223, the second buffer cell 223 from the right (sixth from the left), and the fourth buffer cell from the right (fourth from the left), and the calculation unit 212 is updated. section (buffer 234). Even if the non-zero element positions in the column direction of the parity check matrix are different from the example in FIG.

As described above, by cyclically shifting the intermediate information and writing it back to the shift buffer 211, the reading position of the intermediate information from the shift buffer 211 becomes the same each time. In BP decoding, calculation is performed using information excluding the self node, but the cyclic shift fixes the position of the self node when intermediate information is read. In BP decoding, the calculated intermediate information is used in the next iteration, so buffers are switched (even/odd) between the writing side and the reading side.

<Flow of BP decoding process>
Next, an example of the flow of BP decoding processing executed by the BP decoding device 200 configured as described above to perform BP decoding will be described with reference to the flowchart of FIG.

When the BP decoding process is started, in step S101, the repetition control unit 213 controls the shift buffer 211 and the arithmetic unit 212 to perform initialization processing, inputs the received information r to the circuit, and sets the intermediate information to 0. do. For example, the repetition control unit 213 validates the control signal “receiving data” indicating the input of the received information r, inputs the received information r to the shift buffer 211, and sets the value “0” as the intermediate information zi,j to the shift buffer. 211. Assuming that the code length is N, the repetition control unit 213 completes this process in N cycles. Further, the repetition control unit 213 sets the maximum number of repetitions and sets the count value of the repetition number counter to "0".

In step S102, the repetition control unit 213 controls the shift buffer 211 to perform cyclic shift for one node operation. Further, in step S103, the repetition control unit 213 controls the calculation unit 212 to perform one node calculation.

Such cyclic shift and node operation processing must be performed for each of the 1st to Nth bits of the intermediate information zi,j. Therefore, in step S104, the repetition control unit 213 determines whether or not the processes of steps S102 and S103 have been repeated N times. If it is determined that the number of repetitions has not reached N, the process returns to step S102. That is, the processing from step S102 to step S104 is repeated N times. Then, if it is determined that the cyclic shift and node operation have been performed N times, the process proceeds to step S105.

In step S105, the repetition control unit 213 counts up the repetition number counter.

The repetition control unit 213 controls to repeat the above processing (lmax-1) times. That is, in step S106, the repetition control unit 213 determines whether or not the number of repetitions has reached the maximum value (lmax-1). If it is determined that the number of repetitions has not reached the maximum value (lmax-1), the process returns to step S102. That is, the processing from step S102 to step S106 is repeated until the number of repetitions reaches the maximum value (lmax-1).

Then, when the process from step S102 to step S106 is repeated (lmax-1) times, the process proceeds to step S107.

In step S107, the repetition control unit 213 controls the shift buffer 211 to perform cyclic shift similarly to step S102, and further controls the arithmetic unit 212 to perform node arithmetic similarly to step S103.

In step S108, the calculation unit 212 outputs the decoding result to the subsequent stage.

When the process of step S108 ends, the BP decoding process ends.

As described above, by constructing a storage unit for storing information with a shift buffer using the regularity of codes, wiring congestion caused by an address generator and random access and an address decoder, which were conventionally required, can be eliminated. It becomes unnecessary, and an increase in circuit scale can be suppressed.

For example, when using single-port RAM, only one address can be accessed at a time. In this case, in order to perform a node operation, it is necessary to read information from a plurality of addresses, so it is necessary to execute and update the node operation by reading and writing in a plurality of cycles. However, by using the code regularity as described above, it is possible to limit (fix) one read position and one write position. By doing so, it is possible to transfer information from a predetermined buffer cell directly to the node operation unit according to the sign rule, and to send the node operation result to the next buffer cell. Therefore, node operations can be executed and updated in one cycle. In other words, this makes it possible to reduce the decoding delay.

<Decoding method comparison example>
The graph shown in FIG. 14 shows an example of comparing the bit error rate (BER) and frame error rate (FER) with respect to the signal-to-noise ratio of received information in each decoding method. .

In FIG. 14 , HD indicates majority hard-decision decoding, VTHD indicates variable threshold hard-decision decoding, SD indicates soft-decision decoding, SDHD indicates soft-decision decoding + majority hard-decision decoding, and BP indicates , BP decoding (50 iterations) to which this technology is applied. As is clear from the graph in FIG. 14, by using BP decoding to which this technology is applied, error correction capability can be improved more than other schemes.

That is, by applying the present technology, it is possible to suppress an increase in circuit size while suppressing a decrease in error correction capability. As a result, the BP decoding device 200 can be more easily miniaturized. In addition, it is possible to suppress increases in manufacturing costs and power consumption.

Furthermore, by applying the present technology, processing related to error correction can be facilitated, so an increase in processing time and an increase in power consumption can be suppressed. By suppressing an increase in processing time, it is possible to process received information at a higher bit rate while suppressing a decrease in error correction capability. That is, more highly accurate error correction can be performed for received information having a larger amount of information.

Also, by suppressing an increase in power consumption, an increase in heat generation can be suppressed. Therefore, miniaturization of the housing can be further facilitated. In addition, since deterioration over time can be suppressed, reliability can be improved.

<3. Second Embodiment>
<Shuffled BP Algorithm>
This technology can also be applied to derived algorithms of BP decryption. For example, the present technology can also be applied to a decoding method called shuffled BP decoding that reflects updated information within the same iteration.

An example of this shuffled BP decoding algorithm is shown in FIG. In this case, information calculation is performed as in the following equation (8).

・・・（８）

... (8)

In this case, the information is always updated without switching buffers depending on whether the number of iterations is even or odd. FIG. 16 shows a main configuration example of the shift buffer 211 and the arithmetic unit 212 of the BP decoding device 200 in this case. As shown in FIG. 16, in this case, the selectors 233 and 235, that is, the selectors based on the number of iterations even/odd, are omitted compared to the example of FIG. Also, since the intermediate information of the own node is not used in the next calculation, it is not necessary to record it in the buffer. As an example, three pieces of information A, B, and C are shown in the BP decoding of the first embodiment, but two pieces of information are sufficient in this case. The order of operations may be the same as in the case of BP decoding in the first embodiment.

In this way, by applying the present technology to shuffled BP decoding (Shuffled BP), it is possible to obtain the same effect as in the case of the first embodiment.

<4. Third Embodiment>
<Application of check node operation>
In the BP decoding described above, a Gallager function such as the following equation (9) is used in the check node calculation as in the example of the algorithm shown in FIG.

・・・（９）

... (9)

Such a Gallager function is often implemented using a lookup table (Table Look Up) or the like, and although it is highly accurate, the circuit scale is large and the operation cycle is large. Therefore, the complicated check node operation may be simplified.

For example, as shown in A of FIG. 18, a check node operation may be performed using a Min-Sum algorithm such as Equation (10) below.

・・・（１０）

(10)

Also, for example, as shown in FIG. 18B, the check node operation may be performed using a Normalized Min-Sum algorithm such as Equation (11) below.

α: Normalize Factor
・・・（１１）

α: Normalize Factor
(11)

Also, for example, as shown in FIG. 18C, the check node operation may be performed using an Offset Min-Sum algorithm such as Equation (12) below.

β: Offset Factor
・・・（１２）

β: Offset Factor
(12)

In the case of the BP decoding algorithm in the example of FIG. 17, it was necessary to have a buffer corresponding to the row weight J, but when applying these algorithms, it is sufficient to be able to hold the minimum two values, so the amount of buffer is increased. can be suppressed.

Of course, algorithms other than these may be applied.

In the above description, a difference cyclic code is used as an example of a cyclic code, but the present technology can be applied to any cyclic code.

<5. Fourth Embodiment>
<Receiving device>
FIG. 19 is a block diagram showing a main configuration example of a receiver to which the above-described embodiment is applied. A receiving device 700 shown in FIG. 19 receives a radio signal transmitted from another device, and extracts information contained in the radio signal (the information may be of any kind. For example, image data, etc.). It is a device that restores and outputs As shown in FIG. 19, this receiving apparatus 700 has, for example, an antenna 711, a tuner 712, a demodulator 713, an error corrector 714, a decoder 715, and an output section 716.

Tuner 712 extracts a signal of a desired frequency band (channel) from the radio signal received via antenna 711 and supplies the extracted signal (received signal) to demodulator 713 . The demodulator 713 demodulates the supplied received signal and supplies the obtained demodulated signal to the error corrector 714 .

The error correction unit 714 performs error correction by performing BP decoding on the demodulated signal of the supplied LDPC (Low Density Parity Check) code. The error correction unit 714 supplies the encoded bitstream thus obtained to the decoder 715 .

Decoder 715 decodes the supplied encoded bitstream. Decoder 715 supplies the data obtained by the decoding, that is, the information transmitted from the transmitting side to output section 716 . The output unit 716 outputs the supplied data to the outside. For example, the output unit 716 displays an image corresponding to the image data included in the data on a monitor or the like, outputs sound corresponding to the audio data included in the data from a speaker or the like, or connects an external input terminal or the like. The data is output to another device via the network, the data is stored in a storage medium, and the data is transmitted to another device by wired communication, wireless communication, or the like.

In receiving apparatus 700 configured in this manner, error correction section 714 may have the functions of receiving apparatus 700 described above. For example, the error correction unit 714 may have a configuration similar to that of the BP decoding device 200, and may perform BP decoding by the same method as the embodiments described above with reference to FIGS. 1 to 18. .

By applying the present technology in this way, the receiving apparatus 700 can suppress an increase in circuit scale. As a result, receiving apparatus 700 can more easily have a smaller housing. In addition, it is possible to suppress increases in manufacturing costs and power consumption.

Furthermore, by applying the present technology, processing related to error correction can be facilitated, so an increase in processing time and an increase in power consumption can be suppressed. By suppressing an increase in processing time, it is possible to process received information at a higher bit rate while suppressing a decrease in error correction capability. That is, more highly accurate error correction can be performed on received information having a larger amount of information.

Also, by suppressing an increase in power consumption, an increase in heat generation can be suppressed. Therefore, miniaturization of the housing can be further facilitated. In addition, since deterioration over time can be suppressed, reliability can be improved.

<6. Fifth Embodiment>
<Television receiver>
FIG. 20 shows an example of a schematic configuration of a television apparatus to which the above-described embodiments are applied. The television apparatus 800 includes an antenna 801, a receiving section 802, a demultiplexer 803, a decoder 804, a video signal processing section 805, a display section 806, an audio signal processing section 807, a speaker 808, an external interface (I/F) section 809, a control A unit 810 , a user interface (I/F) unit 811 and a bus 812 are provided.

Receiving section 802 extracts a signal of a desired channel from a broadcast signal received via antenna 801, demodulates the extracted signal, and performs error correction. The receiving unit 802 then outputs the encoded bitstream thus obtained to the demultiplexer 803 . That is, the receiving unit 802 has a role as a transmitting unit in the television device 800 that receives an encoded stream in which images are encoded.

The demultiplexer 803 separates the video stream and audio stream of the program to be viewed from the encoded bitstream, and outputs each separated stream to the decoder 804 . The demultiplexer 803 also extracts auxiliary data such as an EPG (Electronic Program Guide) from the encoded bitstream and supplies the extracted data to the control unit 810 . Note that the demultiplexer 803 may perform descrambling when the encoded bitstream is scrambled.

A decoder 804 decodes the video stream and audio stream input from the demultiplexer 803 . The decoder 804 then outputs the video data generated by the decoding process to the video signal processing section 805 . The decoder 804 also outputs audio data generated by the decoding process to the audio signal processing section 807 .

The video signal processing unit 805 reproduces the video data input from the decoder 804 and causes the display unit 806 to display the video. Also, the video signal processing unit 805 may cause the display unit 806 to display an application screen supplied via a network. Also, the video signal processing unit 805 may perform additional processing such as noise removal on the video data according to the settings. Further, the video signal processing unit 805 may generate GUI (Graphical User Interface) images such as menus, buttons, or cursors, and may superimpose the generated images on the output image.

The display unit 806 is driven by a drive signal supplied from the video signal processing unit 805, and displays an image on the image screen of a display device (for example, a liquid crystal display, a plasma display, an OELD (Organic ElectroLuminescence Display) (organic EL display), or the like). Or display an image.

The audio signal processing unit 807 performs reproduction processing such as D/A conversion and amplification on the audio data input from the decoder 804 and outputs audio from the speaker 808 . Also, the audio signal processing unit 807 may perform additional processing such as noise removal on the audio data.

An external interface unit 809 is an interface for connecting the television apparatus 800 and an external device or network. For example, a video stream or audio stream received via the external interface unit 809 may be decoded by the decoder 804 . That is, the external interface unit 809 also has a role as a transmission unit in the television device 800 that receives the encoded stream in which the image is encoded.

The control unit 810 has a processor such as a CPU and memories such as RAM and ROM. The memory stores programs executed by the CPU, program data, EPG data, data acquired via a network, and the like. The programs stored in the memory are read and executed by the CPU when the television apparatus 800 is activated, for example. By executing a program, the CPU controls the operation of the television apparatus 800 according to an operation signal input from the user interface unit 811, for example.

User interface section 811 is connected to control section 810 . The user interface unit 811 has, for example, buttons and switches for the user to operate the television apparatus 800, a remote control signal receiving unit, and the like. The user interface unit 811 detects an operation by the user through these components, generates an operation signal, and outputs the generated operation signal to the control unit 810 .

A bus 812 interconnects the receiver 802 , demultiplexer 803 , decoder 804 , video signal processor 805 , audio signal processor 807 , external interface 809 , and controller 810 .

In television apparatus 800 configured in this way, receiving section 802 may have the function of receiving apparatus 700 described above. For example, the receiving section 802 may have a configuration of a tuner 712 to an error correcting section 714, and the error correcting process of the control signal performed in the error correcting section 714 may be each of the processes described above with reference to FIGS. BP decoding may be performed by a method similar to that of the embodiment.

By applying the present technology in this way, the television device 800 can suppress an increase in circuit scale. Accordingly, the housing of the television apparatus 800 can be more easily reduced in size. In addition, it is possible to suppress increases in manufacturing costs and power consumption.

Furthermore, by applying the present technology, processing related to error correction can be facilitated, so an increase in processing time and an increase in power consumption can be suppressed. By suppressing an increase in processing time, it is possible to process control information at a higher bit rate while suppressing a decrease in error correction capability. That is, more highly accurate error correction can be performed on control information with a larger amount of information (more sophisticated functions).

Also, by suppressing an increase in power consumption, an increase in heat generation can be suppressed. Therefore, miniaturization of the housing can be further facilitated. In addition, since deterioration over time can be suppressed, reliability can be improved.

<7. Others>
<Software>
The series of processes described above can be executed by hardware or by software. Also, for example, part of the series of processes described above can be executed by software, and other processes can be executed by hardware. When executing (a part or all of) a series of processes by software, a program that constitutes the software is installed in a computer. Here, the computer includes, for example, a computer built into dedicated hardware and a general-purpose personal computer capable of executing various functions by installing various programs.

FIG. 21 is a block diagram showing a configuration example of hardware of a computer that executes (a part of or all of) the series of processes described above by a program.

In a computer 900 shown in FIG. 21, a CPU (Central Processing Unit) 901 , a ROM (Read Only Memory) 902 and a RAM (Random Access Memory) 903 are interconnected via a bus 904 .

Input/output interface 910 is also connected to bus 904 . An input unit 911 , an output unit 912 , a storage unit 913 , a communication unit 914 and a drive 915 are connected to the input/output interface 910 .

The input unit 911 includes, for example, a keyboard, mouse, microphone, touch panel, input terminal, and the like. The output unit 912 includes, for example, a display, a speaker, an output terminal, and the like. The storage unit 913 is composed of, for example, a hard disk, a RAM disk, a nonvolatile memory, or the like. The communication unit 914 is composed of, for example, a network interface. Drive 915 drives removable media 921 such as a magnetic disk, optical disk, magneto-optical disk, or semiconductor memory.

In the computer configured as described above, the CPU 901 loads, for example, a program stored in the storage unit 913 into the RAM 903 via the input/output interface 910 and the bus 904, and executes the above-described series of programs. is processed. The RAM 903 also appropriately stores data necessary for the CPU 901 to execute various processes.

A program executed by the computer 900 can be applied by being recorded on a removable medium 921 such as a package medium, for example. In that case, the program can be installed in the storage unit 913 via the input/output interface 910 by loading the removable medium 921 into the drive 915 .

The program can also be provided via wired or wireless transmission media such as local area networks, the Internet, and digital satellite broadcasting. In that case, the program can be received by the communication unit 914 and installed in the storage unit 913 .

Alternatively, this program can be installed in the ROM 902 or the storage unit 913 in advance.

<Supplement>
Embodiments of the present technology are not limited to the above-described embodiments, and various modifications are possible without departing from the gist of the present technology.

For example, the present technology can be applied to any configuration that constitutes a device or system, such as a processor as a system LSI (Large Scale Integration) or the like, a module using multiple processors or the like, a unit using multiple modules or the like, or other units. It can also be implemented as a set or the like with additional functions (that is, a configuration of part of the device).

Further, for example, each of the processing units described above may be realized by any configuration as long as it has the functions described for the processing unit. For example, any processing unit may be configured by any circuit, LSI (Large Scale Integration), system LSI, processor, module, unit, set, device, apparatus, system, or the like. Also, a plurality of them may be combined. For example, the same type of configuration such as multiple circuits and multiple processors may be combined, or different types of configuration such as a circuit and an LSI may be combined.

In this specification, a system means a set of a plurality of components (devices, modules (parts), etc.), and it does not matter whether all the components are in the same housing. Therefore, a plurality of devices housed in separate housings and connected via a network, and a single device housing a plurality of modules in one housing are both systems. .

Further, for example, the configuration described as one device (or processing unit) may be divided and configured as a plurality of devices (or processing units). Conversely, the configuration described above as a plurality of devices (or processing units) may be collectively configured as one device (or processing unit). Further, it is of course possible to add a configuration other than the above to the configuration of each device (or each processing unit). Furthermore, part of the configuration of one device (or processing unit) may be included in the configuration of another device (or other processing unit) as long as the configuration and operation of the system as a whole are substantially the same. .

In addition, for example, the present technology can take a configuration of cloud computing in which one function is shared by a plurality of devices via a network and processed jointly.

Also, for example, the above-described program can be executed in any device. In that case, the device should have the necessary functions (functional blocks, etc.) and be able to obtain the necessary information.

Further, for example, each step described in the flowchart above can be executed by one device, or can be shared by a plurality of devices and executed. Furthermore, when one step includes a plurality of processes, the plurality of processes included in the one step can be executed by one device or shared by a plurality of devices. In other words, a plurality of processes included in one step can also be executed as processes of a plurality of steps. Conversely, the processing described as multiple steps can also be collectively executed as one step.

A computer-executed program may be such that the processing of the steps described in the program is executed in chronological order according to the order described herein, in parallel, when called, etc. may be executed individually at required timings. That is, as long as there is no contradiction, the processing of each step may be executed in an order different from the order described above. Furthermore, the processing of the steps describing this program may be executed in parallel with the processing of other programs, or may be executed in combination with the processing of other programs.

Each of the techniques described in this specification can be implemented independently and singly unless inconsistent. Of course, it is also possible to use any number of the present techniques in combination. For example, part or all of the present technology described in any embodiment can be combined with part or all of the present technology described in other embodiments. Also, part or all of any of the techniques described above may be implemented in conjunction with other techniques not described above.

Note that the present technology can also take the following configuration.
(1) Storage in which a plurality of pieces of information used for decoding are stored in different areas, and the area for storing the information is shifted in accordance with the computation related to the decoding so as to correspond to the shift in the column direction of the parity check matrix for the decoding. Department and
The information is read out from a predetermined area of the storage unit, the information updated by the decoding operation is rearranged so as to correspond to the shift in the row direction of the parity check matrix, and the information is written in a predetermined area of the storage unit. update department;
An information processing apparatus comprising: an arithmetic unit that performs arithmetic operations related to the decoding using the information read from the storage unit by the update unit, and updates the information.
(2) The information processing apparatus according to (1), wherein the storage unit cyclically shifts the area for storing the information.
(3) The storage unit has a plurality of buffer cells each storing the information, connected in a loop, and by moving the information to the next buffer cell, the area for storing the information is expanded. The information processing device according to (2), which shifts cyclically.
(4) the information is received information input from the outside and intermediate information obtained by calculation related to the decoding;
The information processing according to any one of (1) to (3), wherein the storage unit has a loop of buffer cells for cyclically shifting the received information and a loop of buffer cells for cyclically shifting the intermediate information. Device.
(5) The information processing device according to any one of (1) to (4), wherein the update unit reads the information from an area of the storage unit corresponding to the position of the non-zero coefficient in the column direction of the parity check matrix. .
(6) The information processing device according to any one of (1) to (5), wherein the update unit writes the updated and rearranged information to an area next to the area from which the information was read, in the storage unit. .
(7) The computing unit
a check node calculation unit that performs check node calculation using the information read from the storage unit;
a variable node computation unit that performs variable node computation using the check node computation result obtained by the check node computation unit;
The information processing apparatus according to any one of (1) to (6), further comprising: an information update unit that updates the variable node calculation result obtained by the variable node calculation unit.
(8) The information processing apparatus according to (7), wherein the calculation unit further includes a determination unit that determines occurrence of an error based on the variable node calculation result.
(9) The information processing device according to (7) or (8), wherein the check node calculation unit performs the check node calculation using a Gallager function.
(10) The information processing apparatus according to (7) or (8), wherein the check node calculation unit performs the check node calculation using a Min-Sum algorithm.
(11) The information processing device according to (7) or (8), wherein the check node calculation unit performs the check node calculation using a Normalized Min-Sum algorithm.
(12) The information processing device according to (7) or (8), wherein the check node calculation unit performs the check node calculation using an Offset Min-Sum algorithm.
(13) The information processing device according to any one of (1) to (12), wherein the calculation unit performs calculation related to BP (Belief Propagation) decoding.
(14) The information processing device according to any one of (1) to (12), wherein the calculation unit performs calculations related to Shuffled BP (Belief Propagation) decoding.
(15) Storing a plurality of pieces of information used for decoding in different regions of a storage unit, and storing the regions for storing the information in accordance with the arithmetic operations related to the decoding so as to correspond to the shift in the column direction of the parity check matrix for the decoding. shift the
reading the information from a predetermined area of the storage unit;
performing calculations related to the decoding using the information read from the storage unit, and updating the information;
An information processing method, wherein the updated information is rearranged so as to correspond to the shift in the row direction of the parity check matrix, and the updated information is written in a predetermined area of the storage unit.

200 BP decoder, 211 shift buffer, 212 operation unit, 213 repetition control unit, 221 selection unit, 222 and 223 buffer cells, 231 selection unit, 232 buffer, 233 selection unit, 234 buffer, 235 selection unit, 236 check node operation Section 237 Variable Node Calculation Section 238 Information Update Section 239 Judgment Section 700 Reception Device 711 Antenna 712 Tuner 713 Demodulation Section 714 Error Correction Section 715 Decoder 716 Output Section 800 Television Device 802 Reception Dept. 900 Computer

Claims (15)

a storage unit that stores a plurality of pieces of information used for decoding in mutually different regions, and shifts the region for storing the information according to the computation related to the decoding so as to correspond to the shift in the column direction of the parity check matrix for the decoding;
The information is read out from a predetermined area of the storage unit, the information updated by the decoding operation is rearranged so as to correspond to the shift in the row direction of the parity check matrix, and the information is written in a predetermined area of the storage unit. update department;
An information processing apparatus comprising: an arithmetic unit that performs arithmetic operations related to the decoding using the information read from the storage unit by the update unit, and updates the information. The information processing apparatus according to claim 1, wherein the storage unit cyclically shifts the area for storing the information. The storage unit has a plurality of buffer cells each storing the information, which are connected in a loop, and the area for storing the information is cyclically changed by moving the information to the next buffer cell. The information processing apparatus according to claim 2, wherein the shift is performed. The information is received information input from the outside and intermediate information obtained by calculation related to the decoding,
The information processing apparatus according to claim 1, wherein the storage unit has a loop of buffer cells for cyclically shifting the received information and a loop of buffer cells for cyclically shifting the intermediate information. The information processing apparatus according to claim 1, wherein the updating unit reads the information from a region of the storage unit corresponding to positions of non-zero coefficients in the column direction of the parity check matrix. The information processing apparatus according to claim 1, wherein the update unit writes the updated and rearranged information to an area next to the area from which the information was read, of the storage unit. The calculation unit is
a check node calculation unit that performs check node calculation using the information read from the storage unit;
a variable node computation unit that performs variable node computation using the check node computation result obtained by the check node computation unit;
The information processing apparatus according to claim 1, further comprising an information updating unit that updates the variable node calculation result obtained by the variable node calculation unit. 8. The information processing apparatus according to claim 7, wherein said calculation unit further comprises a determination unit that determines occurrence of an error based on said variable node calculation result. The information processing apparatus according to claim 7, wherein the check node calculation unit performs the check node calculation using a Gallager function. The information processing apparatus according to claim 7, wherein the check node calculation unit performs the check node calculation using a Min-Sum algorithm. The information processing apparatus according to claim 7, wherein the check node calculation unit performs the check node calculation using a Normalized Min-Sum algorithm. The information processing apparatus according to claim 7, wherein the check node calculation unit performs the check node calculation using an Offset Min-Sum algorithm. The information processing device according to claim 1, wherein the computation unit performs computation related to BP (Belief Propagation) decoding. The information processing apparatus according to claim 1, wherein the calculation unit performs calculations related to Shuffled BP (Belief Propagation) decoding. storing a plurality of pieces of information to be used for decoding in different regions of a storage unit, and shifting the region for storing the information according to the computation related to the decoding so as to correspond to the shift in the column direction of the parity check matrix for the decoding;
reading the information from a predetermined area of the storage unit;
performing calculations related to the decoding using the information read from the storage unit, and updating the information;
An information processing method, wherein the updated information is rearranged so as to correspond to the shift in the row direction of the parity check matrix, and the updated information is written in a predetermined area of the storage unit.

Images