JP4965614B2 - Encoding and decoding techniques for packet recovery - Google Patents

Description

The present invention relates generally to packet recovery used in digital communications, and more particularly to an encoding method, decoding method, encoder, and decoder for packet recovery.

In wired or wireless network applications, encoding techniques for packet recovery and corresponding decoding techniques are becoming increasingly important. The reason is that as data transfer rates increase, packet loss occurs more frequently due to detection errors such as header / synchronization patterns and congestion caused by temporary concentration of information on the network switch. This is because the conventional packet recovery method based on retransmission further increases the performance and buffer management overhead.

Interleaving Reed-Solomon (RS) as a prior art to address these issues
A technique for performing encoding in frame units using a block code such as an erasure correction code is well known (Non-Patent Document 1). However, in this conventional technique, when no lost packet exists in a given frame, the redundant packet is wasted without being used.
This inefficiency is improved by increasing the code length, but the amount of calculation related to decoding also increases at the same time.

As another conventional technique, there is a method in which decoding is performed based on a graph structure including a source node and a check node shared by a transmission side and a reception side using a non-organization code specialized for packet recovery (non-decoding code). Patent Document 2). This method is effective in terms of coding rate and is efficient because decoding can be performed in almost linear time. However, the correction efficiency is not good unless the code length is a certain length (amount) or more. Moreover, since the graph structure is random, the mounting efficiency by hardware is not high. Therefore, the application range is limited to the application to streaming media and data distribution using encoding / decoding in software.

Furthermore, as another conventional technique, there is a packet recovery method using a (n, n-1, m) convolutional code (Non-patent Document 3). In this method, lost packet recovery can be performed more flexibly than frame-based techniques using block codes. However, since this method is based on a binary convolutional code, erasure correction for each bit is necessary, so that symbol-by-symbol decoding cannot be performed. Therefore, a large number of decoders need to be arranged in parallel for hardware implementation.

In the above-described prior art, there is a problem that when the efficiency of packet recovery is advanced, the code length becomes long or the implementation of the decoding circuit becomes complicated. Further, if redundant information is added too much, new congestion may occur due to this, so that efficient packet recovery is a very important issue.
Nonnenmacher, EW Biersack, and D. Towsley, `` Parity-basedloss recovery for reliable multicast, '' IEEE / ACM Trans.Networking, vol. 6, pp.349.361, Aug. 1998. Luby, M. Mitzenmacher, A. Shokrollahi, and D. Spielman, '' Efficienterasure correcting codes, '' IEEE Trans. Inform. Theory, vol. 47, pp. 569.584, Feb. 2001. M. Arai, A. Yamaguchi, K. Iwasaki, '' Method to Recover InternetPacket Losses Using (n, n-1, m) Convolutional Codes, '' IEEE Dependable System and Network, pp. 382-389, 2000.

An object of the present invention is to provide a new encoding method and a corresponding decoding method capable of improving the packet recovery rate while effectively utilizing an appropriate amount of redundant information, and a new code for realizing these methods. And a decoder.

In the present invention, a partially-overlapped block (POB) code, which is a new coding scheme configured by combining a plurality of different block codes in a partially overlapping manner, is disclosed. Also, a decoding method corresponding to this encoding method is disclosed. Furthermore, a method for recovering a plurality of packets using this code erasure correction capability is disclosed. According to the present invention, by effectively reusing the redundant information of adjacent frames, the number of packets larger than the number of redundant packets added per frame can be obtained without increasing the asymptotic calculation amount of the decoding algorithm. Allows recovery.

In order to generate the POB code of the present invention, there is provided an encoder comprising means for detecting a frame and means for generating a parity by changing the block code for each subframe, with the overlapping portion as a subframe. Also, means for detecting frames, means for storing the number of overlapping subframes, means for generating a syndrome with a different parity check matrix for each subframe, means for determining a pattern for error correction from packet error position and number information, There is provided a decoder comprising means for calculating an error, means for correcting and decoding the error, and means for recalculating the syndrome from the corrected information.

The present invention will be described in detail below with reference to the drawings. The POB code of the present invention uses a code configuration as shown in FIG. Assuming a configuration in which n symbols are interleaved L times per frame, the codeword w of each frame can be divided into s subframes (wh) including redundant symbols. To do. (Assuming s is divisible by both n and r). In other words, it is assumed that each n / s-symbol subframe includes an r / s redundant symbol.

ここで、

H：生成行列、w：符号語、α：ガロア体の原始元、s：ブロック符号の数（サブフレーム
分割数に等しい）、n:ブロックサイズ、k:情報サイズ、
ただし、k=(n-r)/s、r：パリティサイズ、j：サブフレームの番号それぞれの符号は、必
ずしも現在のフレームではなく、j番目のサブフレームのシンボル集合
wjとそれ以前のs-１個のサブフレームにあるシンボル集合、wj-s-１、wj-s-２、…wj-１
の間に用いられる。iは、符号化の条件の識別のための添え字で、jr/s=<i<(j+１)r/sを満
たす。h*は、h番目のサブフレームのフレーム内での相対的な位置（h*=0,1,2,…,s-1）を
示す。 Different s (n, nr / s) non-binary block codes are encoded so as to satisfy the following parity check condition.

here,

H: generator matrix, w: codeword, α: primitive element of Galois field, s: number of block codes (equal to the number of subframe divisions), n: block size, k: information size,
However, k = (nr) / s, r: parity size, j: subframe number The code of each is not necessarily the current frame, but the symbol set of the jth subframe
wj and the symbol set in s-1 subframes before it, wj-s-1, wj-s-2, ... wj-1
Used during i is a subscript for identifying an encoding condition and satisfies jr / s = <i <(j + 1) r / s. h * indicates a relative position (h * = 0, 1, 2,..., s−1) within the frame of the h-th subframe.

j*や*が付加された他の記号も、h*と同様に定義される。 Decoding is performed in the following steps. Note the jth subframe. S-1 before that
Assuming that the subframes have no packet errors or are all corrected, decoding of the proposed code is similar to erasure correction of a block code. Starting from the syndrome calculation, the symbol information of the lost packet is obtained by using the information of the lost position. i-th syndrome Si (jr / s = <i <(j + 1) added to the end of j-th subframe
) r / s) is calculated by using Hi and the received data wj-s-1, wj-s-2, ..., wj.

Other symbols with j * and * are defined in the same way as h *.

If the total number of lost packets in h subframes starting with subframe j is less than p = rh / s, the lost packets can always be recovered. For example, h-1 following the current subframe
If no packets are lost in a subframe, up to p packets can be recovered. In other words, q (q = <p) packet data be0, be1,
If beq-1 is lost at location e0, e1, ... eq-1, the packet can be recovered by solving the following linear equation similar to RS code erasure correction.

Once all the lost packets in the current subframe are recovered, the syndrome needs to be recalculated at each subframe boundary. This syndrome recalculation step can prevent the calculation cost from increasing while the maximum number of correction packets per frame is r or more. The recalculated new syndrome Si ′ is calculated according to the following formula:

α：ガロア体の原始元、be０、be１、・・・beq-１：q(q=<p)個のパケット情報、
e０,e１,…,eq-１:パケット内の位置

α: primitive element of Galois field, be0, be1, ... beq-1: q (q = <p) packet information,
e0, e1, ..., eq-1: Position in the packet

When the total number h of lost packets in a subframe is greater than p, lost packets cannot be recovered. In this case, consecutive (2s-1) subframes need to be correct in order to restart the packet recovery operation. The asymptotic amount of computation for decryption is
Even if it is not different from the decoding of the block code, in reality, the decoding algorithm must be changed according to the pattern of the number of errors in the subframe. It is important to design properly. In particular, the actual decoding calculation is affected by where in the frame there is a subframe that is currently being corrected. This point needs to be carefully considered for efficient hardware implementation. Reducing the number of multipliers is more important in reducing the circuit size than reducing the number of multiplications.

j番目のサブフレームのデータwjは、以下の関係を満たす。

ここで、どのパリティチェック条件を使うかを示す添え字iは、ｊ番目のサブフレームの
フレーム中の相対位置j*に従って変化する。例えば、
i=j*
と変化させることが出来る。 FIG. 2 shows a code configuration of an embodiment of the POB code. An n = 150 symbol frame is divided into s = 3 subframes (each containing n / s = 50 symbols) and (150, 149) RS
Packet recovery is performed using three codes (parity check conditions are generated by 1, α, and α2, respectively). More specifically,

The j-th subframe data wj satisfies the following relationship.

Here, the subscript i indicating which parity check condition is used changes according to the relative position j * in the frame of the j-th subframe. For example,
i = j *
It can be changed.

Table 1 shows the case where packet recovery can be performed, in correspondence with the number of packets lost in subframes j, j + 1 and j + 2. Depending on the subframe location j * in the frame (position 0, 1,
2) The symbol value be lost at location e is replaced by another lost location e ', e''if necessary.
Can be calculated using.

ケースCの場合、eとe‘が同じサブフレームにあるが、e’‘は次のサブフレームにある。

In case C, e and e ′ are in the same subframe, but e ″ is in the next subframe.

Based on the configuration example of the present invention shown in FIG. 2, the effect of the present invention is shown in FIG. 3 by comparing with other prior art examples. In FIG. 3, the input packet loss probability is shown on the x-axis, and the packet loss probability after using various packet recovery mechanisms is shown on the y-axis. The method of the present invention is (150, 147)
Compared with the method using RS code and the existing method, although the code rate is the same, in the existing method, the maximum number of packets that can be recovered is 3 at the maximum. 5 packets can be recovered. Comparing the method of the present invention with the case where the RS code of (50, 48) is used, the method of the present invention has almost the same recovery capability in a region where the packet loss ratio is small even though the amount of redundant packets is half. It is shown that there is.

Compared to the method of Non-Patent Document 2, it is based on block codes instead of random LDPC codes, so it is suitable for hardware implementation, and is effective even with relatively short code lengths. is there. On the other hand, when the method of the present invention is compared with a method using a binary convolutional code, correction can be performed on a symbol-by-symbol basis, so that hardware implementation efficiency is better compared to packet recovery on a bit-by-bit basis.

Next, a decoding method, an encoder, and a decoder corresponding to the POB code of the present invention will be described. First, the POB coding method will be described again using a specific example. FIG. 4 shows a case where one frame is composed of three subframes and one block code is applied to three subframes. Three block codes are used. The frame is composed of a plurality of packets, and the vertical axis of the figure is the packet width (bit). In the case of encoding information having such a configuration, in (1), a block code is applied from the first subframe to the third subframe of the same frame. In (2), another block code is applied from the second subframe to the first subframe of the next frame. In (3), another block code is applied from the third subframe to the second subframe of the next frame. By applying three different block codes to different ranges in this way, for example, the third subframe is (1), (
2) and (3) will partially overlap.

FIG. 5 shows the parity of (1) after the third subframe, the parity of (2) after the first subframe, and the parity of (3) when parity is generated with the configuration of FIG. FIG. 6 is a configuration diagram after encoding in a case where is added after the second subframe. Of course, where the parity is added is arbitrary.

FIG. 6 is an explanatory diagram when the codeword shown in FIG. 5 is decoded. (1) indicates a range from the first subframe to the parity after the third subframe. (2) indicates a range from the second subframe to the parity after the first subframe of the next frame. (3) shows a range from the third subframe to the parity after the next second subframe. For each of them, each syndrome can be calculated by using a check matrix corresponding to the block code used with the corresponding number in FIG. Accordingly, three syndromes including the information are generated for one subframe. Packet recovery is performed by decoding using these three syndromes.

In the case of a normal block code, (1), (2) and (3) all apply block codes to the same range of information, but the blocks are shifted while overlapping partially as shown in the figure. By applying a code, the error correction capability in units of frames increases. That is, for the same subframe, the first subframe can exhibit the maximum error correction capability when there are no errors in the following two subframes because of the presence of block codes having different ranges while including it. . This means that the parity information of an error-free subframe can be effectively used for error correction of the subsequent subframe. This is more effective by recalculating the syndrome when there is a correctable error. In addition, a specific decoding method can use a method similar to the decoding method of the block code used, but it depends on what subframe is corrected and whether there are some errors in the related syndrome. It is necessary to perform decoding while dividing the case.

The POB coding scheme is a very powerful coding scheme when packet error information can be separately received or detected. The packet error information is information indicating that there is an error in units of packets in the frame, and specifically represents the position and number of packet errors. These may be generated as a flag when the packet is not correctly recognized by the packet detection means as described later, or may be received as detected by another system in the preceding stage of the decoder. . Since these can be received or detected in synchronization with the packet, the means for calculating the packet error information can store the packet error position and count the number of packet errors in the subframe.

<Configuration of encoder>
The encoding flow of the present invention is shown in FIG. First, a signal transmitted in frame units is received (a). A frame of information is detected from the received signal (b). After detecting the frame,
A subframe divided into a predetermined number is detected (c). A packet constituting a subframe is detected (d). Parity is generated in parallel for the number of block codes prepared for different block codes associated with the subframe (e). The last generated parity and original information are output (f).

FIG. 8 shows a configuration example of the encoder 100 corresponding to the flow of FIG. The frame detection means 10
When the header indicating the head of the frame is included in the information, it is detected by pattern matching, and when a control signal synchronized with the head of the frame is obtained separately,
Take advantage of it. The same applies to the subframe detection 12 and the packet detection means 14. In particular, when the frame structure is determined in advance, subframes and packets can be detected by a counter synchronized with the head of the frame. Since a plurality of different block codes are encoded for one subframe, as many parity generating means as the number of block codes to be used are required. However, it should be noted that it does not depend on how the block code is selected. As a specific circuit configuration, only the number of parity bits or symbols generated by the selected block code is required. In FIG. 8, this is displayed in an overlapping manner. These are processed in parallel. As the parity generation means, registers 16 having feedback units are prepared for the corresponding number of block codes, and are installed in parallel. The input to the feedback register 16 may be from the beginning or the back of the register. The configuration of the feedback register 16 depends on the type of block code used. The subframe detection result is connected to the selector 18 at the end of the shift register, and it is determined which parity is to be output after which subframe. The selector 20 at the final stage is for outputting information and parity in an arbitrary format.

<Decoder configuration>
A decoder for receiving and decoding information encoded by the POB encoding method of the present invention has the following configuration, for example.
1. Frame detection means 2. 2. Subframe detection means Packet detection means4. Different for each of the plurality of received information blocks to be encoded associated in a subframe,
And means for calculating a syndrome using a check matrix corresponding to the block code used in the encoding.
5. 5. Means for recalculating the corresponding syndrome and obtaining the correct syndrome when error correction is possible in the subframe temporally prior to the subframe of interest 6. Means for detecting and receiving packet error number and packet error position, which are packet error information Means for determining whether error correction is possible from the position of the subframe and the number of packet errors, and generating an error from the recalculated syndrome when error correction is possible.
8). Means for correctly decoding the generated error when error correction is possible.
10. Output means.

The decoding flow of the present invention is shown in FIG. FIG. 10 shows a configuration example of the decoder 200 corresponding to the flow of FIG. After receiving the signal (a), the frame is first detected (b). Next, a subframe is detected (c). A packet constituting a subframe is detected (d). When a packet error is detected, the number and position of packet errors are stored in the packet error register, and the number of errors in the subframe is counted (36). These are input to coefficient calculation means 48 and error correction availability determination means 50 (FIG. 10) for calculating an error. On the other hand, for the information block associated with the subframe, a syndrome is calculated using a check matrix corresponding to the block code used in the encoding (e). Since one subframe is included in a plurality of block codes, the same number of syndrome calculations as the block codes to be used are required as in the case of parity generation at the time of encoding. The syndrome calculation is performed in parallel. As described in the configuration of the encoder, in the POB encoding method, there is a case where there are a plurality of syndromes used in one block code because it does not depend on how to select a block code to be used. Therefore, as the specific circuit configuration, the number of syndromes used in one block code is required.

After the syndrome is calculated, out of the syndromes that include the subframe of interest,
The syndrome used in error correction of the previous subframe in terms of time needs to be recalculated (f) when the error can be corrected in the temporally previous subframe. In this way, recalculate all syndromes containing information prior to the subframe of interest (f)
Then, an error is obtained using the syndrome (g). Next, it is determined whether error correction is possible (i). If error correction is impossible, a flag is set to notify that the information includes an error (j). If error correction is possible, an error is obtained and correction decoding is performed (k). If correction is possible at this time, as described above, the error used for correction is fed back to the syndrome recalculation when correcting the next subframe (m). Finally, it is output by the output means (l). The error flag may not be output.

The decoder 200 of FIG. 10 includes a frame detection unit 30, a subframe detection unit 32, and a packet detection unit 34, as in the case of the encoder of FIG. The packet generator 38 calculates a syndrome for each packet. The parity check matrix corresponding to the block code used in the encoding is
It can be composed of a linear feedback shift register. Therefore, as the packet generation means, the linear feedback register 38 for syndrome calculation is prepared for the number of different block codes. Separately, the input information is stored in the buffer 44. A plurality of syndromes are stored in the syndrome register 40. The syndrome is recalculated (42) using the result of error correction of the previous subframe. Then, the correct syndrome is input to the coefficient calculation means 48 of an expression for obtaining an error. Here, the data from the syndrome register 40 to the syndrome recalculation (42) may be sent serially or in parallel.

On the other hand, when a packet error is detected by the packet detector 34 or when packet loss information is received in the preceding circuit of the decoder, the error position of the packet is stored (36
At the same time, the number of packet errors in the subframe is counted (36). The information on the packet error position is input to the coefficient calculation means 48 of an equation for obtaining an error, and the coefficient is calculated together with the recalculated syndrome (42). The number of packet errors is input to the correctability determination unit 50, and it is determined whether the error can be corrected. As described below, whether or not error correction is possible is determined by PO.
Determined from the structure of the B code. When error correction is possible, the error generation means 52 calculates an error. As a result, the information in the buffer 44 is corrected (54) and output. At this time, if there is an error, it is stored in the error register 58, and feedback 60 for syndrome recalculation is performed via the selector 46 for error correction of the next subframe as described above. In addition, FIG.
At 0, the error register 58 may be removed and the contents of the syndrome register 40 may be updated by feeding back the result of the syndrome recalculation (42). Thereby, the circuit scale can be reduced.

Here, the case where the packet recovery shown in Table 1 can be performed will be further described. When there are three overlapping parities for one subframe and there is position information of packet error, a maximum of three packet recovery can be performed per subframe. However, for that purpose, it is essential that there is no error in the next subframe (j + 1) and the next subframe (j + 2) (case D). Combinations that can be corrected are Case A to Case D,
For example, when there is only one error in the current subframe, correction is possible regardless of the number of errors in other subframes. Further, in the case where these four error corrections are possible, the coefficient for generating an error differs depending on the number of the subframe in the frame. Since there are three syndromes for a maximum of three errors, three simultaneous equations will be solved. This solution can be solved analytically for cases A to D. Also, the coefficient varies depending on the current subframe number in the frame.
These are judged from the number of errors, and an error coefficient is obtained.

The error coefficient can be obtained by calculating the denominator and the numerator. In particular, the circuit for calculating the reciprocal of the denominator becomes large. For this reason, the circuit scale can be remarkably reduced by sharing the numerator calculation and the reciprocal calculation of the denominator, and further sharing the multiplication part of the reciprocal of the numerator and denominator. An example in which the circuit scale can be reduced is shown in FIG. In addition, since the syndrome is involved only in the calculation of the molecule, the input of the syndrome may be connected to the common molecular calculation part.

<When RS code is used as a block code>
Reed-Solomon code (RS code) often used as a non-binary block code
It can be used as a block code of POB code. Specifically, one packet is divided into symbol widths used in the RS code, and the RS code is applied so that only the packet width is interleaved. A plurality of codes are prepared as RS codes, and a parity is generated by applying different RS codes to ranges that partially overlap each other associated with subframes.

FIG. 12 shows a configuration when RS code is applied. One packet is divided into symbol widths used in the RS code. With such a symbol width, an RS code is calculated within a range shown in (1), (2), and (3) of FIG. 4 to generate a parity. The number of subframe divisions is arbitrary. The configuration of the RS code is also arbitrary. Therefore, a plurality of parities may be generated. As an example, as shown in FIG. 4, the subframe is divided into three, and the RS code is (n,
If n-1) code is used, one parity is generated. If three different RS codes are added by multiplying 1, α, α2 using α, which is the basis of an appropriate Galois field, three RS codes are used.
Since the codes are different from each other, a POB code can be configured. Especially RS code with 1 as the root is 1
The first subframe or the third subframe is multiplied, and the RS code having α as the root is applied from the second subframe to the first subframe of the next frame, and RS having the α2 as the root. The code is applied from the third subframe to the second subframe of the next frame.

A flowchart of the encoding method in this case is shown in FIG. Encoder 30 corresponding to the method
The configuration of 0 is shown in FIG. In FIG. 13, signal reception (a), frame detection (b), subframe detection (c), packet detection (d), and output (f) are the same as in FIG. In FIG. 14, the same components as those in FIG. RS codes are used as block codes, and three different RS codes are prepared, using 1, α, α2 as the root of the code, using the primitive element α of an appropriate Galois field GF (2m) To do. Parity is generated for the entire subframe in the range to be subjected to the RS code associated with the subframe (e). The method of arranging the parity is arbitrary, and these are output as the encoding result. Linear feedback shift register 16 used
The feedback portion is provided with a multiplier of 1, α, α2, and the constant can always be multiplied and fed back so that the parity can be calculated by the shift register 16. Note that the start points of the three shift registers are shifted by subframes. Therefore, the subframe detection result is connected to the selector 18 at the end of the shift register, and it is determined which parity is to be output after which subframe. The selector 20 at the final stage is for outputting information and parity in an arbitrary format.

Next, the decoder will be described. Transmission information to which parity corresponding to three different RS codes is added is received, and syndromes are generated from the parity check matrix corresponding to each RS code. The flowchart is shown in FIG. FIG. 15 is basically the same as FIG. Now, we have prepared three RS codes with 1, α, α2 as the code roots. If the syndromes obtained from these parities are s0, s1, and s2, errors are obtained from these and packet error position information. It is done. Since the packet is divided into a plurality of symbols, a syndrome just divided is obtained for one frame.

FIG. 16 shows the configuration of the decoder 400 corresponding to the flow of FIG. The configuration of FIG. 16 is basically the same as that of FIG. When the RS code is used, the syndrome calculation circuit can be specifically configured by a feedback register 38 in which the code roots 1, α, α2 are connected as a multiplier 70. The syndrome is stored in the register, and is input to the coefficient calculation means 48 of the equation for calculating the error by performing the syndrome recalculation (42) from the error correction result of the previous subframe.
On the other hand, the number of packet errors and the packet error position, which are packet error information, are received (36).
Then, the packet error position information is input to the coefficient calculation means 48 of an equation for obtaining an error. As shown in FIG. 8, an error can be calculated from the recalculated syndrome and packet error position, and an error-correctable pattern is selected from the information on the number of packet errors as shown in Table 1. Table 1
Equations for obtaining an error are specifically obtained from the cases A to D and the position of the subframe to be corrected, and the coefficient of the equation is generated. Finally, through the final stage multiplier 72 illustrated in FIG.
An error is calculated. When the error is calculated, the error correction is performed by multiplying the coefficient according to the packet error position and the subframe position and adding to the information in the buffer 44. This is performed for all symbols in the packet, and the decoding result is output (56). If the error can be corrected, it is fed back to the circuit (42) for recalculating the syndrome through the error register 58 for correction of the next subframe.

<Pob Code Encoder and Decoder as Concatenated Code>
The POB coding method is a very effective coding method for packet recovery. However, if this is a concatenated code with the outer code as an outer code, it becomes a more powerful coding method. In this case, an arbitrary code scheme such as a convolutional code can be selected as the inner code, but it is often composed mainly of a block code (such as a Hamming code, a BCH code, and an RS code). FIG. 17 shows a frame configuration diagram of a concatenated code in which the POB code method is an outer code. One block code is applied to one packet, and the parity is added to the end of the packet. Therefore, when viewed from the POB code, if the codeword to which the inner code is applied is regarded as one packet, it is the same as the conventional POB code system. Accordingly, the flowchart and the circuit configuration in this case are obtained by adding an encoder and a decoder of a block code that is an inner code. By adding such an inner code, it is possible to expect an improvement in correction capability for a random error in the packet. Furthermore, since packet errors can be reliably extracted, it is possible to reduce the circuit scale of a POB code decoder that is an outer code. In addition, it is possible to cover within a closed circuit configuration without obtaining packet error information from the outside.

FIG. 18 shows a flowchart, and FIG. 19 shows a circuit configuration 500 thereof. In FIG. 18, signal reception (a), frame detection (b), subframe detection (c), packet detection (d) and output (g) are the same as in FIG. 7, but the parity generation part (e), ( f) is very different. The outer code is generated in the same way (e), but in parallel with it, the parity of the inner code for one packet is generated (f). Although parallel in FIG. 18, a serial method in which the inner code is performed first and the outer code is performed later may be used. However, since the information part of the packet is used for parity generation for both the outer code and the inner code, it is advantageous in terms of processing speed to process in parallel as shown in the figure. In addition, the inner code is prioritized for the portion where the parity overlaps. That is, after the parity of the POB code which is the outer code is generated, the inner code for the parity is generated. Finally, the encoding result is output (g).

The basic configuration of FIG. 19 is the same as that of FIG. FIG. 19 also has a feature in the parity generation part as in the flowchart of FIG. Similar to the description of the flowchart, the parity generation means 80 for the POB code which is the outer code and the parity generation means 82 for the inner code perform processing in parallel. The inner code encoder uses the same linear feedback register 84 as the outer code linear feedback register 16.
This is also used when a block code is used like the outer code.

FIG. 20 shows a configuration example of the decoder 600. In the encoder, the inner encoder and the outer encoder can be configured either in series or in parallel. However, in the decoder, an inner code decoder 90 and an outer code decoder 92 are configured in series. Since the inner code 90 handles information in packet units and is encoded with an arbitrary block code, a general block code decoding method can be used. However, when there is a packet error and correction is not possible, the position of the packet error is detected. Also, the number of packet errors indicating how many packet errors were uncorrectable for each subframe is detected and output. The POB code decoder 92 which is an outer code receives the packet and the packet error information and performs decoding using these.

<Internal code decoder>
FIG. 21 shows an inner code decoder 700. When a block code is used as the inner code, the syndrome can be calculated by combining the linear feedback register 38. Inner codes are often used to correct random errors in packets, so in many cases,
A block code for correcting a plurality of bit errors is used. Therefore, a plurality of parity bits are prepared in order to perform a plurality of error corrections. The corresponding number of syndromes are calculated and stored in the syndrome register 40. The coefficient of the error position polynomial is obtained from the calculated syndrome (48), and the error is obtained. If correction is possible, the error in the packet is corrected from the obtained error and the packet is output. If the correction is impossible, the packet is output without correction, and the uncorrectable flag and the position information of the packet in the subframe are output. That is, the two pieces of information of the packet error flag and the packet error position are collectively output as packet error information separately from the packet that is the reception information. In FIG. 21, there is a buffer register 44. However, in the case of an inner code decoder, it is only necessary to have a buffer having a packet size. In the inner code decoder, the decoding algorithm may be the general method of the block code used. The features of the concatenated code with the POB code are that a packet error flag is generated and a position in a subframe is extracted and output.

<Decoder of outer code (POB code)>
As described above, the error-corrected packet and the packet error information are input from the inner code decoder. Since the block code used in the POB code system has how many packet errors are within such a range, and information on the position of the error is input, it can be realized with the same configuration as in FIG.

The present invention has been described with reference to FIGS. However, the present invention is not limited to these examples. It will be apparent to those skilled in the art that any modification can be made without departing from the spirit of the present invention.

It is a figure which shows the code structure of the POB code | symbol of this invention. It is a figure which shows the code | symbol structure of one Example of the POB code | symbol of this invention. It is a figure which shows the recovery effect of the packet at the time of using the POB code system of this invention. It is explanatory drawing about the POB code system of this invention. FIG. 5 is a diagram illustrating a configuration after parity is generated in the configuration of FIG. 4. It is explanatory drawing in the case of decoding the codeword shown in FIG. It is a figure which shows the flow of an encoding of this invention. It is a figure which shows the structural example of the encoder 100 corresponding to the flow of FIG. It is a figure which shows the flow of a decoding of this invention. FIG. 10 is a diagram illustrating a configuration example of a decoder 200 corresponding to the flow of FIG. 9. It is a figure which shows that a circuit scale can be made small by sharing the last multiplication part. It is a figure which shows the structure at the time of applying the RS code of this invention. It is a figure which shows the flowchart of the encoding method of FIG. It is a figure which shows the structure of the encoder corresponding to the flow of FIG. It is a figure which shows the flow of decoding in the case of RS code. It is a figure which shows the structure of the decoder corresponding to the flow of FIG. It is a figure which shows the frame block diagram of the concatenated code which made the POB code system the outer code. It is a figure which shows the flow of the encoding method in the case of FIG. It is a figure which shows the structure of the encoder corresponding to the flow of FIG. It is a figure which shows the structure of the decoder in the case of FIG. It is a figure which shows the structure of the decoder of the inner code of FIG.

10, 30 Frame detection means 12, 32 Subframe detection means 14, 34 Packet detection means 16, 38, 84 Linear feedback register 18, 20, 46, 86 Selector 36 Packet error position and number detection means 40, 44 Register 48 Error Coefficient calculation means 50 for determining the equation 50 Correction possibility determination means 52 Error generation (calculation) means 58 Error register 72 Multiplier 80 Outer encoder 82 Inner encoder 100, 300, 500 Encoder 200, 400, 600 Decoder

Claims (8)

Detecting a frame including a plurality of packets;
Detecting a subframe in the detected frame;
Detecting a packet in a subframe;
Calculating a syndrome for a block code corresponding to a subframe;
Recalculating the syndrome in response to the fact that a packet in a temporally previous subframe among the plurality of subframes corresponding to the calculated syndrome can be error-corrected ;
A method for decoding packet information including:   The method of claim 1, wherein calculating the syndrome includes calculating a number of syndromes corresponding to the number of different block codes provided overlapping the subframe. The method of claim 1, wherein the block code is a Reed-Solomon (RS) code, and the step of calculating the syndrome calculates a syndrome Si using the following equation:

here,

H: generator matrix, w: code word, α: primitive element of Galois field, s: number of block codes,
n: block size, i: syndrome number,
j: Subframe number, where jr / s = <i <(j + 1) r / s 4. The method of claim 3, wherein the step of recalculating the syndrome calculates a syndrome S ′ using the following equation:

here,
α: primitive element of Galois field, be0, be1, ... beq-1: q (q = <p) packet information,
e0, e1, ..., eq-1: position in the packet Means for detecting a frame including a plurality of packets;
Means for detecting subframes in the frame;
Means for detecting a packet in a subframe;
Means for generating a syndrome for a block code corresponding to a subframe;
Means for regenerating the syndrome in response to the fact that a packet in a temporally preceding subframe can be error-corrected among a plurality of subframes corresponding to the generated syndrome;
A decoder comprising: Means for detecting an error position in the packet using the generated syndrome;
Means for generating a packet error using the generated syndrome;
Means for outputting a result decoded using an error position in the detected packet and an error of the generated packet;
The decoder of claim 5 further comprising: The syndrome generation means includes:
A linear feedback register for generating a parity corresponding to each of at least two different block codes for one subframe;
A register holding the generated syndrome; and
The decoder of claim 5 comprising:   The decoder according to claim 7, wherein the syndrome regeneration unit regenerates a syndrome using an error generated in a temporally previous subframe among a plurality of subframes corresponding to the generated syndrome.

Images