JP5371623B2 - Communication system and receiving apparatus - Google Patents

Abstract

<P>PROBLEM TO BE SOLVED: To provide a communication system which performs decoding while shortening delay time by shortening decoding time. <P>SOLUTION: Upon input of a received packet to a receiver 20, a sequential decoding part 22 performs sequential EXOR calculation, implements Gaussian elimination, and when a rank of a subsequent matrix becomes equal to a dissipation packet, performs EXOR calculation for the remaining dissipation packet. <P>COPYRIGHT: (C)2011,JPO&amp;INPIT

Description

  The present invention relates to a communication system that employs a low density parity check (LDPC) code as an erasure error correction code.

  In a conventional erasure correction encoding / decoding communication system, a transmission device includes a packet generation unit, an erasure correction encoding unit, and a transmission unit, while a reception device includes a reception unit, a decoding unit, and an information bit reproduction unit. . The erasure correction encoding unit of the transmission apparatus encodes information bits in units of packets using, for example, an LDPC code as the erasure correction code, and transmits the information bit from the transmission unit to the communication path. The receiving unit of the receiving apparatus receives a packet sequence that is partially lost due to the communication path, and decodes the lost packet using a Gaussian elimination method or the like based on the packet that the decoding unit has successfully received (for example, Patent Document 1). reference).

First, a general conventional decoding method is shown.
In general, the erasure correction code is decoded by a Gaussian elimination method. Hereinafter, the Gaussian elimination method will be briefly described. For simplicity of explanation, it is assumed that each packet is composed of 1-bit information. Actually, each packet contains multiple bits of information, and the same processing is executed in parallel.

Let codeword v = (u | p), u = (u ₁ u ₂ ... U _k ) be an information vector, and p = (p ₁ p ₂ ... P _m ) be a parity vector.
For example, if the matrix A is expressed by the following equation (1) and the information vector u = (u ₁ u ₂ u ₃ u ₄ ) = (0 1 0 1), the correct parity vector is p ^T = A · u ^T = (P ₁ p ₂ p ₃ ) = (1 0 0).
Now, assuming that the reception packet success in the receiving apparatus is (u ₁ , u ₂ , p ₂ , p ₃ ) = (0, ₁ , 0, 0), p ₂ and p ₃ are the second line of the formula (1) and In order to correspond to the third row, the matrix for calculation of Expression (2) is prepared using those rows. Note that a method for generating the matrix A as shown in Expression (1) will be described in the second embodiment.

A Gaussian elimination method is applied to the calculation matrix shown in the above equation (2) to convert it into a matrix of the following equation (3) including the lower triangular matrix as a right half submatrix. From the matrix of the following equation (3), backward substitution is performed using (u ₁ , u ₂ , p ₂ , p ₃ ) = (0, 1, 0, 0), and (u ₃ , u ₄ ) = (0 , 1) can be solved.

Based on the above calculation method, in actual communication, the decoding unit of the receiving apparatus performs decoding in the following procedure.
[Conventional decryption procedure]
(Procedure 1) After receiving a packet, error detection of the packet is performed.
(Procedure 2) In the above (Procedure 1), if there is an error (lost packet), nothing is done.
(Procedure 3) In the above (Procedure 1), if there is no error, the reception success packet is stored in the buffer of the decoding unit. When a parity packet is received, a Gaussian elimination method is performed, and it is confirmed whether the number of lost packets in the information packet is equal to the rank of the matrix after the Gaussian elimination method according to the processes of the above equations (2) and (3).
(Procedure 4) In the above (Procedure 3), if the ranks are not equal, the next reception success packet is awaited.
(Procedure 5) In the above (Procedure 3), if the ranks are equal, the storage of the reception success packet is stopped, and all the receptions succeeded according to the matrix after the Gaussian elimination method according to the processing of the above formulas (2) and (3) The lost packet is calculated using the packet.

International Publication WO2007 / 0727221

Since the conventional decoding procedure is as described above, the decoding unit collectively performs decoding after determining that all lost packets can be decoded by checking the rank of the Gaussian elimination method. Therefore, there is a problem that the EXOR calculation of packets is concentrated at a time, and the calculation time becomes dominant in transmission delay. FIG. 15 shows a decoding time T _dec from “rank OK” at the time of determination of decoding start to decoding completion when performing the conventional decoding procedure.

The present invention has been made to solve the above-described problems. By receiving a received packet input to a receiving device, the calculation time is distributed by sequentially performing EXOR calculation, and the decoding time T _dec is shortened. It is an object of the present invention to provide a communication system that performs decoding capable of reducing the delay time.

  In the communication system according to the present invention, each time a receiving apparatus receives a bit or packet received from a transmitting apparatus, the receiving apparatus has a vector that stores an EXOR value for each row of a parity check matrix of an erasure correction code. The EXOR calculation is performed on a row position where one of the columns corresponding to the received value corresponds to the value stored in each row position corresponding to the vector storing the EXOR value for each row. A sequential decoding unit for adding values is provided.

According to the present invention, each time a bit or packet received from a transmitting device is received, the received value for that bit or packet is stored in the EXOR value for each row of the parity check matrix of the erasure correction code. 1 of the corresponding column and EXOR calculation with a row position, and the value stored for each corresponding row position of the vector storing the EXOR value for each row is added to the currently calculated value. Therefore, as soon as the received packet is input, a receiving device capable of executing decoding that can reduce the delay time by distributing the calculation time by performing sequential EXOR calculation and shortening the decoding time T _dec is provided. A communication system can be provided.

It is a block diagram which shows the structure of the communication system which concerns on Embodiment 1 of this invention. FIG. 10 is an explanatory diagram showing a decoding time when the sequential decoding procedure according to the first embodiment is performed. 6 is an explanatory diagram showing a matrix after a Gaussian elimination method of a sequential decoding procedure according to Embodiment 1. FIG. It is a graph which shows the reduction effect of the decoding time by the sequential decoding procedure of Embodiment 1 compared with the conventional decoding procedure. The graph which shows the reduction effect of the decoding time by the sequential decoding procedure of Embodiment 1 compared with the conventional decoding procedure is shown, the conventional decoding procedure is a non-systematic code, and the sequential decoding procedure is a systematic code. In the encoding process according to Embodiment 2 of the present invention, an example of a puncture position with an encoding rate of 2/3 is shown. FIG. 7 is an explanatory diagram showing puncturing according to Embodiment 2, in which FIG. 7A is a mother code and FIG. 7B is a punctured code. FIG. 8A shows a parity check matrix subjected to an extension operation according to Embodiment 2, FIG. 8A shows the structure of the extended parity check matrix, and FIG. 8B shows an extended basic matrix. 6 is a diagram illustrating an example of a parity check matrix of an LDPC code according to Embodiment 2. FIG. It is a figure which shows the result of having performed the process of step 1 of the erasure | elimination correction encoding method of Embodiment 2 with respect to the check matrix shown in FIG. FIG. 11 is a diagram illustrating a result of performing the processing in step 2 of the erasure correction coding method according to the second embodiment on the parity check matrix illustrated in FIG. 10. FIG. 12 is a diagram illustrating a result of performing the processing in step 3 of the erasure correction coding method according to the second embodiment on the parity check matrix illustrated in FIG. 11. It is a figure which shows the result of having performed the process of step 4 of the erasure | elimination correction encoding method of Embodiment 2 with respect to the check matrix shown in FIG. 6 is a diagram showing a matrix A generated by the erasure correction coding method according to Embodiment 2. FIG. It is explanatory drawing which shows the decoding time at the time of performing the conventional decoding procedure.

Embodiment 1 FIG.
1 is a block diagram showing a configuration of a communication system according to Embodiment 1 of the present invention. The communication system shown in FIG. 1 uses an LDPC code as an erasure error correction code. The transmission device 10 used as a transmitter includes a packet generation unit 11, an erasure correction coding unit 12, and a transmission unit 13, while the reception device 20 used as a receiver includes a reception unit 21 and a sequential decoding. The unit 22 and the information bit reproduction unit 23 are provided.

In transmission apparatus 10, packet generation unit 11 generates a packet from information bits using a check matrix. The erasure correction encoding unit 12 performs erasure error correction encoding on the packet. The transmission unit 13 transmits the encoded packet to the reception device 20 via the communication path 1. Details of the transmitting apparatus 10 will be described in the second embodiment below.
In the reception device 20, the reception unit 21 receives a packet transmitted from the transmission device 10 via the communication path 1. The sequential decoding unit 22 has a buffer for temporarily storing received packets, and detects and erasures these packets according to the following sequential decoding procedure. The information bit reproducing unit 23 combines the decrypted packets to generate information bits.

Hereinafter, the operation of the sequential decoding unit 22 of the receiving device 20 will be described.
[Sequential decoding procedure]
(Procedure 1) After receiving the packet by the receiving unit 21, the sequential decoding unit 22 detects an error of the packet.
(Procedure 2) In the above (Procedure 1), the sequential decoding unit 22 does nothing if there is an error (lost packet).

(Procedure 3) If there is no error in the above (Procedure 1), the sequential decoding unit 22 temporarily stores the reception success packet in the buffer, and “1” in the column corresponding to the reception success packet. EXOR calculation is performed with the stored value already calculated for each line where the Also, the sequential decoding unit 22 deletes the column corresponding to the information packet that has been successfully received from the matrix A ^, and generates the matrix A.
For example, the EXOR calculation when the information packet u ₁ = 0 that has been successfully received is expressed by the following equation (4). Here, the matrix A ^· is a matrix obtained by deleting the column corresponding to the information packet that has been successfully received from the matrix A, and the vector R is a vector indicating the EXOR value for each row.
For the information packet u ₂ = 1 that has been successfully received following u ₁ , the calculation is sequentially performed every time the packet is received as shown in the following equation (5). As shown in Expression (5), EXOR calculation is performed between the information packet u ₂ that has been successfully received and the row position where “1” is in the column of the corresponding check matrix A, and the value stored in the vector R And the currently calculated value. Again, the column corresponding to the information packet successfully received from the matrix A ^· is deleted.

Also, if the receiving unit 21 receives the parity packet p _m, sequential decoding unit 22, the number of lost packets in the information packet u _k, it is constituted by the row corresponding to the successfully received parity packet for matrices A ^· Matrix and rank of the matrix a ^··· performing the Gaussian elimination method to a ^·· is whether to confirm or equal.
For example, when the information packets u ₃ and u ₄ and the parity packet p ₁ are lost and the parity packets p ₂ = 0 and p ₃ = 0 are received, the sequential decoding unit 22 applies the Gaussian elimination method to the following equation (6). Go to get the following formula (7) and check the rank.

(Step 4) sequential decoding unit 22 in the above (step 3), if not equal the rank of the lost packet number and the matrix A ^{· · ·} of the information packet and waits for the next successful reception packet.

(Step 5) sequential decoding unit 22 in the above (step 3), if equal rank, to stop storing successful reception packet, in accordance with matrix A ^{· · ·} after vector R and Gaussian elimination, successfully received Calculate lost packets using all packets.
For example, when the information packet u ₁ = 0, u ₂ = 1 is received, the information packet u ₃ , u ₄ and the parity packet p ₁ are lost, and the parity packet p ₂ = 0, p ₃ = 0 is received, the matrix A since ^... is above formula (7), sequential decoding unit 22 obtains each row of EXOR value the formula so as to correspond to the matrix ^{a ...} (represented by the following formula (8)) (9). Thus, since the following equation (10) is obtained, (u ₃ , u ₄ ) = (0, 1) can be solved by backward substitution.

FIG. 2 shows a decoding time T _dec from the time when the rank is confirmed by performing the Gaussian elimination method in the case of performing the above-described sequential decoding procedure (“rank OK” in the figure) to decoding completion. . As shown in FIG. 2, since the division calculation can be realized by sequentially decoding according to the above-described procedure, the decoding time T _dec can be significantly reduced as compared with the conventional decoding procedure shown in FIG.

Next, the logical effect is verified.
FIG. 3 shows a matrix after the Gaussian elimination method. For such a matrix, the conventional decoding procedure calculates all the information packet lengths at once, so that all EXOR calculations for the information packet length are required. Therefore, the time required for the EXOR calculation for the information packet length and the time required for the Gaussian elimination method are T _dec .
On the other hand, in the sequential decoding procedure according to the first embodiment, since the calculation of the reception success packet portion is completed at the time when each reception success packet is input, the EXOR calculation is performed after the determination of “rank OK”. Only the lost packet length is required. Therefore, the time required for the EXOR calculation for the lost packet length and the time required for the Gaussian elimination method are T _dec .

上式（１１）の第１項は、ガウス消去法に対する比率を１０％とした場合の固定の計算時間を設定し、第２項は、ＥＸＯＲ計算の比率を９０％とし、その中でガウス消去法後の残った行数が消失パケット数／情報パケット数に比例し、計算量もその値に比例するよう設定している。 Now, assuming that the number of encoded packets (number of information packets) is 100, the encoded packet size is 1.28 kbytes, the decoded packet unit is 1 Mbit, and the conventional decoding throughput is 1 Gbps (lost packet / information packet = 1). A simple calculation method of the decoding time T _dec is shown below.

The first term of the above equation (11) sets a fixed calculation time when the ratio to the Gaussian elimination method is 10%, and the second term sets the EXOR calculation ratio to 90%, of which the Gaussian elimination The number of lines remaining after the law is set to be proportional to the number of lost packets / number of information packets, and the calculation amount is also set to be proportional to the value.

上式（１２）に示す逐次復号の場合、受信成功パケットは逐次計算終了しているため、従来法の上式（１１）からさらに消失パケット数／情報パケット数に比例して第２項の計算量を削減できる。 On the other hand, a calculation method in the case of the sequential decoding procedure according to the first embodiment is shown below.

In the case of the sequential decoding shown in the above equation (12), since the successful reception packet has been sequentially calculated, the calculation of the second term is further proportional to the number of lost packets / number of information packets from the above equation (11). The amount can be reduced.

FIG. 4 is a graph showing the effect of reducing decoding time by the sequential decoding procedure of the first embodiment, compared with the conventional decoding procedure. Note that the throughput of the conventional Gaussian elimination method is assumed to be about 1 Gbps, and that value is used as a reference in the graph of FIG. A delay of decoding time T _dec = 1 ms occurs with an information amount of 1 Mbit under 1 Gbps.
As can be seen from FIG. 4, a delay time reduction effect of 10 to 50% can be expected at points other than lost packet / information packet = 1.

  In addition, when the sequential decoding procedure according to the first embodiment is executed assuming a systematic code, the number of rows in the Gaussian elimination method is reduced in proportion to lost packets / information packets. Thus, there is a possibility that the throughput as shown in FIG. 5 can be expected. FIG. 5 is a graph showing an effect of improving the throughput by the sequential decoding procedure of the systematic code as compared with the conventional decoding procedure of the non-systematic code. Also in this estimation, the decoding packet unit is assumed to be 1 Mbit and the conventional decoding throughput is 1 Gbps (lost packet / information packet = 1) as in FIG.

As described above, according to the first embodiment, a communication system including the transmission device 10 that performs erasure correction code encoding for erasure correction and the reception device 20 that performs erasure correction code decoding for bits or packets. Each time, the sequential decoding unit 22 of the receiving device 20 has a vector R for storing an EXOR value for each row with respect to the parity check matrix A of the erasure correction code, and whenever the bit or packet received from the transmitting device 10 is received, Exor calculation is performed on a bit or packet with a row position where “1” is in the column corresponding to the received value, and a value stored for each corresponding row position of the vector R and a currently calculated value are It comprised so that it might add. Further, the sequential decoding unit 22 deletes all the columns of the check matrix A of the information part that has been successfully received from the bits or packets for which the EXOR calculation has been performed, and deletes all the rows of the parity check matrix of the parity part. create a matrix a ^{· · ·} including lower triangular matrix by Gaussian elimination for matrices a ^{· ·,} and configured to play the lost information part based on the matrix a ^{· · ·.} Further, the sequential decoding unit 22 is configured to perform the erasure correction process when the rank of the matrix A ^... Generated by performing the Gaussian elimination method becomes equal to the lost information part.
For this reason, calculations performed in a lump in the conventional decoding procedure can be sequentially calculated as soon as the received packet is input, so that calculation time can be distributed. As a result, the time from rank OK to completion of decoding (T _dec ) can be shortened, and a decoding process capable of shortening the delay time becomes possible.

Embodiment 2. FIG.
Here, an actual example of the erasure correction LDPC code used in the communication system described in the first embodiment is shown. Note that the communication system according to the second embodiment has the same configuration as that of the system shown in FIG. 1, and will be described below with the aid of FIG. 1 as necessary.

また、行列Ｈはｍ_ｂ×ｎ_ｂの２元基礎行列Ｈ_ｂを拡張して構成する。ここで、ｎ＝ｎ_ｂ×ｚ，ｍ＝ｍ_ｂ×ｚである。 First, the basic description of the structured LDPC code will be described. The structured parity check matrix H of the LDPC code is defined by the following equation (13). The matrix H is m × n, where n is the codeword length and m is the parity length. The information length k is k = n−m.

Further, the matrix H is configured by expanding the _binary basic matrix H _b of m _b × n _b . Here, n = n _b × z and m = m _b × z.

そして、基礎行列Ｈ_ｂは、下式（１５）に示す、ｍ_ｂ×ｎ_ｂ行列である。

The base matrix H _b is expanded by replacing the element “1” therein with a z × z permutation matrix and the element “0” with a z × z zero matrix. By varying the expansion factor z, a set of LDPC codes having various information lengths and specific coding rates can be obtained.

The basic matrix H _b is an _mb × _nb matrix shown in the following equation (15).

Thus, all can be described with few parameters due to the structural features of the parity check matrix. This feature results in low complexity. Actually, when encoding / decoding is realized by the transmission device 10 and the reception device 20, only the base matrix _Hb is required instead of the parity check matrix H.

Next, structured LDPC mother code sets having different code sizes will be described. In order to generate an LCPC code set having various code lengths and arbitrary coding rates, a fixed basic matrix H _b ^uniform is defined. This fixed basic matrix H _b ^uniform is corrected to generate a corrected basic matrix H _b ^modified . Then, a basic matrix having an arbitrary code size is obtained from the corrected basic matrix H _b ^modified .

ここで、

This will be specifically described. Now, the coding rate of the designed mother code set is ½, and the information length can be set from 144 to 6000 (can be extended) in 12-bit steps. That is, the information length k = 144, 144 + 12, 144 + 2 × 12, 144 + 3 × 12,..., 6000 can be set. The size of the basic matrix is 12 × 24, and m _b = 12 and n _b = 24. Therefore, the expansion factor z can be adjusted step by step from 12 to 500. Then, a fixed basic matrix H _b ^uniform of an LDPC code set with a coding rate of 1/2 is defined as in the following equation (16).

here,

Incidentally, in the above equation _{(18), T D} of ^{H b parity} is Dual Diagonal matrix defined by the following equation (19).

In order to obtain an LDPC code having an arbitrary code length, the fixed basic matrix H _b ^uniform of the above equation (16) is corrected to generate a corrected basic matrix H _b ^modified . This defines a parity check matrix of an LDPC code by an expansion factor z. The value of h _ij ^b is corrected for elements other than “−1” of the matrix H _b ^uniform .

Here, (h _ij ^b ) _modified is an element of the i-th row and j-th column of the ^modified basic matrix H _b ^modified . Also, _let (h _ij ^b ) _{uniform be} the element of the i-th row and j-th column of the standard basic matrix H _b ^uniform . Then, (h _ij ^b ) _modified is defined as the following equation (20).

In the above equation (20), z _max is the maximum expansion factor, and z _max = 500 (expandable). This expansion factor z is uniquely determined according to the codeword length.

  Next, a method for supporting multiple coding rates will be described. The erasure correction coding unit 12 performs puncturing from the LDPC mother code block to obtain a coding rate higher than ½. Also, the coding rate lower than 1/2 is realized by performing a check matrix expansion operation, as will be described in detail later.

  First, a puncturing operation for obtaining a coding rate higher than a coding rate 1/2 will be described. As a basic design policy, the information block size of the mother LDPC code is made as close to k as possible. This is to make use of the characteristics of structural LDPC mother codes of various codeword lengths. If the information block size of the mother code is always larger than k, it is necessary to add a few “0” bits before the information block size k. Thereafter, the LDPC mother code is encoded. Finally, it is necessary to delete these additional “0” bits and to delete a certain number of codeword bits in order to generate a codeword of codeword length n.

The encoding process of the (n, k) punctured LDPC code requires the following three steps.
(Step 1) The expansion factor z is calculated. The expansion factor z is given by the following equation (21). From the fixed basic matrix H _b ^uniform and the expansion factor z, an (m _b × z, n _b × z) LDPC mother code can be obtained. Here, m _b = 12 and n _b = 24.

(Step 2) x = k _b × z−k “0” bits are added before the information length k to construct an information block of k _b × z bits of the mother code. Then, an encoding process of (m _b × z, n _b × z) mother code is executed to generate m _b × z parity bits. Here, x is always smaller than z.

(Step 3) The “0” bit added in (Step 2) above is deleted. If the codeword length after this deletion does not match n, it is necessary to puncture y = m _b × z−n + k parity bits at a predetermined location.

The position of the puncture is one of the important factors that influence the performance of the punctured LDPC code. Therefore, it is necessary to choose carefully. FIG. 6 shows an example of a puncture position with a coding rate of 2/3. Mother code is divided into n _b number of partial, each portion includes a z bits. These are expressed by describing the position label of the portion including the bits of the mother codeword block from 0 to n _b × z−1.

  FIG. 7 is an explanatory diagram showing code puncturing by the above-described three steps. FIG. 7A is a mother code and FIG. 7B is a punctured code. The new codeword length of the codeword is n. The corresponding information length is given by k. As a result, the coding rate r is k / n.

As a result, the erasure correction coding unit 12 implements the following three steps to realize an arbitrary coding rate and code length that are larger than the coding rate 1/2.
(Step 1) The expansion factor z is calculated according to the calculation formula (21). Then, (m _b × z, n _b × z) LDPC mother code can be obtained from the fixed basic matrix H _b ^uniform and the expansion factor z. Here, m _b = 12, n _b = 24, and k _b = n _b −m _b = 12.

(Step 2) x = k _b × z−k “0” bits are added before the information length k to construct an information block of k _b × z bits of the mother code. Then, an encoding process of (m _b × z, n _b × z) mother code is executed to generate m _b × z parity bits.

(Step 3) The “0” bit added in (Step 2) above is deleted. If the codeword length after this deletion does not match n, it is necessary to puncture y = m _b × z−n + k parity bits at a predetermined location by the following procedure.
(Step 3-1) When the coding rate r = 1/2, the y bit at the end of the codeword block is deleted.

(Step 3-2) When the coding rate r> 1/2, define the puncture pattern vector P of size _{m b} in the following equation (22). The elements of the vector P are different integers of from m _b to n _b -1, the order of the substitution patterns of these elements of the vector P is predefine. Here, the size of the basic matrix _Hb is 12 × 24.
P = [17, 19, 21, 23, 25, 27, 31,
29, 18, 24, 22, 28, 30, 20, 26] (22)

Next, the following parameters are defined.
k = floor (y / z), m = y mod z (23)

The position label of the part including the bits of the mother codeword block from 0 to n _b × z−1 is written and expressed, and the puncture positions of y deletion bits of the mother codeword block are defined as follows: .
P (0) × z: (P (0) +1) × z−1,
(1-th z bits deleted),
P (1) × z: (P (1) +1) × z−1,
(2-th z bits deleted),
...
(...),
P (k−1) × z: (P (k−1) +1) × z−1,
(K-th z bits deleted),
P (k) × z: P (k) × z + m−1,
(M bits deleted) (24)

  Next, an extended operation for obtaining a coding rate lower than the coding rate 1/2 will be described. In order to obtain a coding rate lower than the coding rate 1/2, the erasure correction coding unit 12 performs an extension operation on the parity check matrix of the LDPC mother code with the coding rate 1/2. FIG. 8A shows the structure of the extended parity check matrix.

The encoding process of the (n, k) extended LDPC code requires the following three steps.
(Step 1) In order to calculate Δm and obtain an extended basic matrix H _b ^{uniform_extension} (Δm) of size (m _b + Δm) × (n _b + Δm), Δm rows and Δm columns are the last of the standard basic matrix H _b ^uniform Add to the last row and column. Δm is shown in the following equation (25), and the entire extended basic matrix H _b ^{uniform_extension} (Δm) after extension is shown in FIG.

(Step 2) The expansion factor z is calculated.
(Step 3) The extended basic matrix H _b ^{uniform_extension} (Δm) is corrected to the H _b ^{modified_extension} (Δm) by the above equation (20). Here, H _b ^{modified_extension} (Δm) is a basic matrix of ((n _b + Δm) z, k _b z) LDPC code.

Next, an efficient erasure correction coding method using the LDPC code will be described.
The parity check matrix H _b ^{uniform_extension} (Δm = m) of the LDPC code shown in the second embodiment is defined by an expression replaced by the following equation (26). An example of the ^parity check matrix H _b ^{uniform_extension} is shown in FIG. Here, for simplification of description, an example in which m _b = 3 and z = 5 will be described.

Here, when H _b ^parity in the above equation (26) has a configuration in which a diagonal matrix having a row weight of 2 is stepped as in the following equation (27), the generation matrix is expressed by the following steps. create.

(Step 1) First, the first row and the z + ^1th row of H _b ^{uniform_extension} are added. Next, the second row and the z + 2 row are added. Repeat this z times. Thereby, the unit matrix is formed from the z + 1-th row to the z + z-th row of H _b ^parity . FIG. 10 shows the result of performing the process of step 1 on the parity check matrix shown in FIG.

(Step 2) Next, using the rows from z + 1 to z + z obtained in (Step 1), z + i (i = 1, 2,..., Z) as in (Step 1) above. The row and the 2z + i row are added. This operation is repeated until the end of the addition of the m _b × z-th row. FIG. 11 shows the result of performing the process of step 2 on the parity check matrix shown in FIG.

(Step ^₃₎ addition and rows of _H ^{b parity} corresponding to the very first row to the _{T D} leftmost column of ^{H b parity} is "1" standing, a row of the next _H ^{b parity.} Next, go to the addition in the same manner for the column you are standing is "1" in the second of T _D. By repeating this operation, the partial matrix of T _D is the identity matrix. FIG. 12 shows the result of performing the process of step 3 on the parity check matrix shown in FIG.

(Step 4) Next, the first row and the m _b × z + 1 row are added using the matrix (shown in FIG. 11) obtained as a result of the above (Step 3). Subsequently, the second row and the m _b × z + second row are added. This is repeated m _b × z times. FIG. 13 shows the result of performing the process of step 4 on the parity check matrix shown in FIG.

With the above procedure, the parity check matrix H _b ^{uniform_extension} can be converted into the form of the following equation (28). Among these, the matrix A is shown in FIG.

As the generation matrix G, G = [I | A] is generated by the matrix A shown in FIG. Erasure correction coding section 12 generates an encoded packet as c = u · G ^T by directly using the matrix G. Here, u is an information packet series.
Further, the erasure correction encoding unit 12 may obtain only the parity part of the codeword c by using only the matrix A by p ^T = A · u ^T. In the sequential decoding procedure by the sequential decoding unit 22 of the first embodiment, decoding calculation is performed based on this matrix A.

  As described above, according to the second embodiment, since the erasure correction coding unit 12 is configured to generate an LDCP code having an arbitrary code length and coding rate, the LDPC code described in the second embodiment is used. Thus, it is possible to exhibit erasure correction capability with better performance than using the LDPC code described in the first embodiment.

  DESCRIPTION OF SYMBOLS 1 Communication channel, 10 Transmission apparatus, 11 Packet generation part, 12 Erasure correction encoding part, 13 Transmission part, 20 Reception apparatus, 21 Reception part, 22 Successive decoding part, 23 Information bit reproduction | regeneration part

Claims (4)

For a bit or packet, in a communication system comprising a transmitting device that encodes an erasure correction code for performing erasure correction, and a receiving device that decodes the erasure correction code,
The receiving device is:
A column that stores an EXOR value for each row of the parity check matrix of the erasure correction code, and each time a bit or packet received from the transmitter is received, a column corresponding to the received value for the bit or packet A sequential decoding unit that performs an EXOR calculation with a row position of 1 and adds a value stored for each corresponding row position of the vector storing the EXOR value for each row and a currently calculated value. A communication system characterized by the above. The sequential decoding unit of the receiving device
In the bit or packet for which the EXOR calculation has been performed, all the check matrix columns of the information part that has been successfully received are deleted, all the check matrix rows of the parity part are deleted, and the remaining matrix is reduced by Gaussian elimination. 2. The communication system according to claim 1, wherein a triangular matrix, an upper triangular matrix, or a diagonal matrix is generated, and the lost information portion is reproduced based on the matrix. The sequential decoding unit of the receiving device
The erasure correction process is performed when the rank of the lower triangular matrix, the upper triangular matrix, or the diagonal matrix generated by performing the Gaussian elimination method is equal to the number of packets of the lost information portion. Communication system.   A bit or packet that has been encoded from the erasure correction code and transmitted from a transmitter that encodes the erasure correction code for performing erasure correction on the bit or packet is received to decode the erasure correction code. A receiving device for performing,
  Each time the bit or packet received from the transmitting device is received, the received value corresponding to the bit or packet corresponds to the received value. A sequential decoding unit that performs an EXOR calculation with a row position in which one of the columns is located, and adds a value stored for each corresponding row position of the vector storing the EXOR value for each row and a currently calculated value; A receiving apparatus comprising:

Images