Method for efficient interleaving of variable length packets with maximized block size

[0002] The present invention relates to digital communication channels, and more particularly, to a method for efficient interleaving of variable length packets.

[0003] In many communication channels, errors appear in bursts, i.e., a single error event has more than one erroneous data element (bit, byte, symbol or other). Error bursts occur because of various reasons, among them burst noise in a channel, error bursts in the output of a Viterbi decoder and others. Error bursts are usually undesirable because most decoders cannot efficiently handle many neighboring errors. An interleaver is a device that allows for the spreading of the error from a burst into separated “single” errors by performing permutations on the data elements. For example, when block coding (such as Reed-Solomon) is used the interleaver allows for spreading of the error burst between a few codewords, thus relaxing the error correction requirements of the code.

[0004] A very common and simple interleaver is the block interleaver. In this interleaver, the data elements (bits, bytes, symbols or others) are placed into a two-dimensional table row-wise and are read out of the table column-wise. The block size (i.e., the number of rows multiplied by the number of columns) is typically constrained by the memory resources of the interleaver.

[0005] In a packet network, variable-length packets of data are transmitted through a communication channel. The packet size is often greater than the block size. In this case, the packet is divided into segments that are smaller than or equal to the interleaver block size. Each segment is then separately interleaved. A trivial way to perform this segmentation is make all segments but the last one, equal to the interleaver block size. The last segment will then be smaller than the block size. The disadvantage of this method is that the last segment can be very small for certain packet lengths. This results in poor performance of the interleaver.

[0006] The present invention provides a method for efficient interleaving of variable-length packets. In packet networks, block interleaving of variable-length packets can be inefficient when the interleaver block size is fixed and smaller than the packet size. The reason is that for certain packet lengths, the remaining number of elements for the last block (i.e., bytes or symbols) can be very low.

[0007] The method of the present invention calculates the optimal interleaver block sizes for a known packet length, which may be variable, and a known (or selected) interleaver width size.

[0008] FIGS. 1 and 2 are flow diagrams of described embodiments of the invention.

[0009] An interleaver is a device that allows for the spreading of the error from a burst into separated “single” errors by performing permutations on the data elements in a data packet. For example, when block coding (such as Reed-Solomon) is used the interleaver allows for spreading of the error burst between a few codewords, thus relaxing the error correction requirements of the code.

[0010] A very common and simple interleaver is the block interleaver. In this interleaver, the data elements (bits, bytes, symbols or others) are placed into a two-dimensional table row-wise and are read out of the table column-wise. The block size (i.e., the number of rows multiplied by the number of columns) is typically constrained by the memory resources of the interleaver.

[0011] In a packet network, variable-length packets of data are transmitted through a communication channel. The packet size is often greater than the block size. In this case, the packet is divided into segments that are smaller than or equal to the interleaver block size. Each segment is then separately interleaved. A trivial way to perform this segmentation is make all segments but the last one, equal to the interleaver block size. The last segment will then be smaller than the block size. The disadvantage of this method is that the last segment can be very small for certain packet lengths. This results in poor performance of the interleaver.

[0012] The reason that calculating block sizes is more efficient than just picking a block size and letting the tail (last block) be whatever size it turns out to be is as follows: The burst tolerance of a block (i.e. the longest noise burst that can hit a block and from which data can still be recovered) is T*I bytes, where T is the Reed-Solomon (RS) correction factor, and I is the interleaver depth of the block. The burst tolerance for a packet is determined by its “weakest” block, i.e. the block with the lowest interleaver depth. Therefore, it is desirable that the last block not have a low interleaver depth (possibly 1), and this is achieved by the methods of the present invention.

[0013] This invention calculates the sizes of the segments for a data packet, such that the sizes of all segments are nearly equal and still as large as possible. The number of columns is known or fixed, and preferably equals to the codeword length. Formulas are used to calculate the number of rows in each segment as a function of the packet length, codeword length and maximum block size.

[0014] The present invention provides a simple calculation of optimal interleaver block sizes for a given packet length with the constraint of maximizing the interleaver block size. That is, the present invention provides a method for maximizing burst noise tolerance of a packet by spreading data into approximately equal interleaver blocks rather than having a few fixed size blocks and one small “end” block with a small amount of data (e.g. a low interleaver depth). A first embodiment is shown in FIG. 1.

[0015] For the formulas of the present invention, the following notation is used:

[0016] Packet length in elements (e.g. bits, bytes, symbols, etc.): N_f

[0017] Interleaver width (typically codeword length): N_r

[0018] Maximum block size (in elements): B_r

[0019] Total number of interleaver rows in the packet: I_tot⁰=ceil(N_f/N_r),

[0020] where “ceil(x)” is a function that rounds “x” to the nearest integer in a positive infinity direction.

[0021] Maximal number of rows per segment (such that the interleaver block does not exceed B_r): I_r,max=floor(B_r/N_r),

[0022] where “floor (x)” is a function that rounds “x” to the nearest integer in a negative infinity direction.

[0023] Number of segments: N_s⁰=ceil(I_tot/I_r,max)

[0024] Then for a segment m, the formula for calculating the maximum number of rows, I_r^mis as (m=1 . . . N_s⁰): follows: $I_r^m=\mathrm{ceil}\left(I_{\mathrm{tot}}^{\left(m-1\right)}/N_s^{\left(m-1\right)}\right)$ $N_s^m=N_s^{\left(m-1\right)}-1$ $I_{\mathrm{tot}}^m=I_{\mathrm{tot}}^{\left(m-1\right)}-I_r^m$

[0025] An example using this formula is as follows: N_f=2100, N_r=200, B_r2048

[0026] I_tot⁰=ceil(N_f/N_r)=11

[0027] I_r,max=floor(B_r/N_r)=10

[0028] N_s⁰=ceil(I_tot/I_r,max)=2

[0029] I_r¹=ceil(I_tot⁰/N_s⁰)=6

[0030] N_s¹=N_s⁰−1=1

[0031] I_tot¹=I_tot⁰−I_r¹=5

[0032] I_r²=ceil(I_tot¹/N_s¹)=5

[0033] N_s²=N_s¹−1=0

[0034] I_tot²=I_tot¹−I_r²=0

[0035] For this example, optimal segmentation has been achieved. That is, for this example two blocks each having five rows has been calculated (interleaver depth of five). Although the maximum block size, B_r, was selected, these formulas may also be used to optimize the block size, or alternatively, several block sizes may be employed and the one with optimal (maximum) interleaving depth selected for use.

[0036] An alternative formula (shown in FIG. 2) may have the following form. This formula results in the same segment sizes, but in a different order.

[0037] The prior notation is again used, where:

[0038] Packet length: N_f

[0039] Codeword length: N_r

[0040] Maximal block size: B_r

[0041] Total number of interleaver rows: I_tot⁰=ceil(N_f/N_r)

[0042] Maximal number of rows per segment: I_r,max=floor(B_r/N_r)

[0043] Number of segments: N_s⁰=ceil(I_tot⁰/I_r,max)

[0044] Interleaver depth of first block: I_r¹=floor(I_tot⁰/N_s⁰)

[0045] No. of blocks with depth of I_r¹: M=N_s⁰·(I_r¹+1)−I_tot⁰

[0046] Then for a segment i, the formula for calculating the maximum number of rows, I_r⁽ⁱ⁾is as follows: (i=1 . . . N_s⁰): $I_r^{\left(i\right)}=\{\begin{array}{cc}{I}_r^1,& i=1,\dots ,M\\ I_r^1+1,& i=M+1,\dots ,N_s^0\end{array}$

[0047] The packet consists of N_s⁰interleaver segments (blocks) and the width (number of columns) of each segment is N_r. The depth (number of rows) in the first M segments is I_r¹. The depth of the rest of the segment is I_r¹1.

[0048] An example, using this alternative formula is as follows:

[0049] N_f=2100, N_r200, B_r=2048

[0050] I_tot⁰=ceil(N_f/N_r)=11

[0051] I_r,max=floor(B_r/N_r)=10

[0052] N_s⁰=ceil(I_tot/I_r,max)=2

[0053] I_r¹=floor(I_tot⁰/N_s⁰)=5

[0054] M=N_s⁰−(I_tot⁰−N_s⁰·I_r¹)=1

[0055] For this example, the results are: I_r¹=5, I_r²=6

[0056] That is, for this example, two blocks with one having five rows and one having six rows was calculated. Again, optimization on block size may be performed. Other such formula may be generated in a similar fashion to calculate interleaver block sizes for a given packet length while maximizing the block size.

[0057] The present invention is capable of being implemented in software, hardware, or combinations of hardware and software. Having thus described in a few particular embodiments of the invention, various alternations, modifications, and improvements will readily occur to those skilled in the art. Such alternations, modifications and improvements as are made obvious by this disclosure are intended to be part of this description though not expressly stated herein, and are intended to be within the spirit and scope of the invention. Accordingly, the foregoing description is by way of example only, and not intended to be limiting. The invention is limited only as defined in the following claims and equivalents thereto.