Design of Packet-Based Block Codes with Shift Operators

This paper introduces packet-oriented block codes for the recovery of lost packets and the correction of an erroneous single packet. Specifically, a family of systematic codes is proposed, based on a Vandermonde matrix applied to a group of information packets to construct redundant packets, where the elements of the Vandermonde matrix are bit-level right arithmetic shift operators. The code design is applicable to packets of any size, provided that the packets within a block of information packets are of uniform length. In order to decrease the overhead associated with packet padding using shift operators, non-Vandermonde matrices are also proposed for designing packet-oriented block codes. An efficient matrix inversion procedure for the off-line design of the decoding algorithm is presented to recover lost packets. The error correction capability of the design is investigated as well. The decoding algorithm, based on syndrome decoding, to correct a single erroneous packet in a group of received packets is presented. The paper is equipped with examples of codes using different parameters. The code designs and their performance are tested using Monte Carlo simulations; the results obtained exhibit good agreement with the corresponding theoretical results.

Real-time applications are delay sensitive and, in the Internet, are primarily based on user datagram protocol (UDP). Packet-level forward error correction (FEC) is a packet loss recovery technique which does not require retransmissions and allows packet delivery with bounded delay and controllable reliability [1]. In order to protect information packets, additional redundancy packets are also sent. The term "packet" is loosely applied in this context, as in many proposals, packet-level FEC is used at the data-link layer. Packet-level FEC aims at recovering some of the lost packets, where the lost packets originate from erroneous bit transmissions and packet discarding at the lower protocol layers, especially for multihop networks, as well as from congestions in the network and buffer overflows. When packet level FEC is deployed alone to recover from lost packets, the packet loss rate (PLR) is reduced compared to the PLR in the network. However, there is no guarantee that all packets will be recovered at the destination. This is acceptable in some applications like video and audio streaming or multicasting protocols [2].

The parity packets in the existing packet-level FEC schemes are constructed in a similar fashion as parity bits/symbols in the linear block codes used in digital transmission systems, except the bits used in the encoding process are from different packets. The receiver is able to recover up to a certain number of lost/erroneous packets in a block of transmitted packets governed by the minimum distance of the code [1, 3].

There are a number of powerful and efficient FEC schemes to recover from erasures and/or errors [4], such as low density parity check (LDPC) codes and tornado codes, which use bipartite graphs [2, 5]. Also, Reed Solomon (R-S) codes are used in many applications. However, the codewords in these codes are rather short, and this dictates the construction of the parity packets, which are usually visualized as arranging information packets row-wise and running the FEC code column-wise [6, 7]. An alternative to this is to use the turbo codes to construct the turbo code frame, and then split the frame into packets. This is only feasible in turbo codes because of the large size of the codewords [8].

In practical applications, in addition to erasure/error recovery capability of the code, another important aspect to consider is the complexity of the encoding and decoding processes [9]. This aspect motivates the investigations in this paper, where the only operations permitted on packets are arithmetic packet shifts and binary additions. Particularly, this paper focuses on systematic codes with coefficient matrices based on the Vandermonde or NonVandermonde structures. Both designs, by incorporating packet shifts, facilitate fast matrix-vector multiplication and efficient inversion of submatrices involved in the erasure or erroneous packet recovery processes. In contrast to other systematic erasure codes based on Vandermonde matrices, the proposed codes are not using Vandermonde matrices to manipulate elements (packet fragments) from the Galois field (GF), but rather use them to operate on whole packets by working with their shifts. The benefit of this approach is the lower encoding and decoding complexities of the designs presented in this paper. The proposed codes are maximum distance separable (MDS) and, while maintaining comparable performance as in the more conventional ones, are also quite flexible in the choice of the code rate.

In conventional applications of systematic codes to packet-level FEC, a unit of information, either symbol or bit, , , is taken from each of the information packets. These symbols are used to construct parity symbols with the help of the coefficient matrix . The parity symbols are then transmitted in redundancy packets. The coded/transmitted symbols on packets, represented by the column vector , are calculated at the transmitter (encoder) using the following linear system of equations:

where is the column vector of information symbols from packets, is the generator matrix, and is the identity matrix. For R-S codes, the matrix multiplication in (1) uses GF arithmetics. In general, if all information packets are of the same length , (1) is used times to construct the coded packets, where is the number of bits represented in each symbol and is the floor operator. The assumption used in this paper is that all packets in the coded group are of the same length. This imposes some limitations which can be overcome by padding the packets to the same length. For brevity of notation, for all symbols in the group of packets, we rewrite (1) using the packet version of this relationship as:

where is a matrix of information packets arranged in rows, each with symbol elements, and is the corresponding matrix of coded packets.

At the receiver side, for MDS codes, if there are lost information packets, we have to solve the following system of equations for :

or equivalently, determine

where is the vector of any received packets, is a submatrix of with rows corresponding to the received packets as determined by the received packets sequence numbers, and represents the inverse of a matrix. There are many matrix inversion techniques that could be used, such as those based on Cramer's rule procedure, Gaussian elimination, or Gaussian Jordan elimination methods [10–12]. We will present later a suitable technique for our designs for finding the matrix inverse efficiently for the proposed codes.

The main challenge in the design of an erasure code is to determine , or in the case of systematic codes, the corresponding coefficient matrix . For MDS codes, the matrix should be designed in such a way that any submatrix, , has to be invertible (full rank). The total number of such submatrices is , where represents the -choose- operator. The simplest two designs of G are the repetition code and the single parity check code. In the former case, the code is where is the column vector of all 1's, while the latter is the code which adds one more packet consisting of the parity check of all information packets; that is, is the row vector of all 1's. These two codes, though simple to use, are not the best, since the former has a low rate while the latter recovers at most only one missing packet. In the case of the systematic codes considered in this paper, there are other matrices that could be used as resulting in the desired properties of being invertible, such as the Cauchy and Vandermonde matrices. We will discuss next the Vandermonde matrix which is used as the coefficient matrix in the R-S erasure codes. The Vandermonde matrix is also utilized in the design of the proposed code in this paper, but with a different building element than in the case of R-S codes.

The Vandermonde matrix , with elements, is given by the following [13]:

This matrix is proven to be nonsingular if the parameters , for , are distinct. For R-S erasure codes with , the elements are taken from the extended GF, GF(), where is a prime number ( is used most of the time) and is any integer ( is used for highest efficiency to represent a byte). Therefore, multiplication and addition operations in (2) and in (4) must be done on that extended GF. As a result, the following problems are encountered when working with R-S codes for packet-level FEC: (i) the code rates (parameters) are limited and (ii) the encoding and decoding processes are computationally intensive. Moreover, it has been shown that the Vandermonde matrix, based on the elements taken from the finite GF, is not always nonsingular [13–15].

In the rest of the paper we deal with the processing of packets; however, some of the concepts involved are very close to symbol processing in FEC codes. Therefore, we will follow commonly accepted symbols and terms to denote corresponding operations.

In this section, we present a code design using a coefficient matrix , based on the Vandermonde matrix, which (i) results in computationally efficient processing of long packets, and (ii) possesses the desired properties when performing the decoding procedure in the proposed MDS code using (4). We choose the elements in the Vandermonde matrix as in (5) to be , for , where stands for a right arithmetic shift operator by bits applied to the row information packet , represented in bits from now on. Therefore, the coefficient matrix, , in our code is given by:

To ensure that this Vandermonde matrix, consisting of the arithmetic shifts operators , when applied to the information packets, results in packets that can be recovered, the packet size has to be increased by at least over the original information packet size by zero padding these packets to the size of [4]. This packet size ensures that the arithmetic shifts implement delay (not cyclic shifts). Therefore, the overall effective rate for code is . For example, when applying the proposed design to Ethernet frames with transmission units of bytes and using the code , the effective code rate is which is close to the conventional rate 1/2 of this code. With the proposed coefficient matrix as in (6), based on (2) and (4), the encoding process and packet loss recovery process in the proposed codes are described in Sections 3.1 and 3.2, respectively.

3.1. Encoding Process

The Vandermonde-based matrix that is augmented with the identity matrix (systematic code) comprise the generator matrix of the code which is given by:

where is the designed matrix. For the proposed systematic MDS code, the encoder uses (2) and (7) to get:

where are the coded packets comprising , where the first of them are the original information packets. The remaining packets are generated by modulo- addition of all the information packets after a proper shift of each information packet. Because of similarities with the construction of codewords in cyclic codes [6], it is natural to interpret (8) as a system of polynomial equations. In this system of algebraic equations, with being represented as a polynomial , the product is a right shift, where is the right shift by bits. The addition of polynomials with binary coefficients corresponding to bits in the packets is a modulo-2 addition. For brevity of notation, we will use to describe the polynomial representation of a packet.

As compared to conventional encoding processes based on (1) and (2), the encoding process in (8) is fast and efficient because it uses just shifting and modulo- addition operations of packets. This may benefit hardware implementation of the proposed packet coding or, in software implementation, reduce the number of memory accesses. Because of the invertibility properties of the Vandermonde matrix and its submatrices concatenated with the identity matrix, when we get any coded packets out of transmitted ones, all the original information packets can be recovered, at the receiver side [13]. Therefore, the minimum distance of such code is , which is an MDS code with a small overhead because each packet is padded with zeros. These codes can correct for errors or erasures [1].

3.2. Decoding Process

Initially we assume that the packet is either received correctly or lost. Assume that out of the received packets, some are information packets indexed by and some are parity packets indexed by . If the total number of packets received is greater than or equal to , of these packets, including all the received information packets, are used to construct the vector in (4). The submatrix is obtained from the generator matrix by knocking off the rows of corresponding to packets not used or lost during transmission. Moreover, since some of these received packets are information packets, their corresponding rows and columns in can be removed so that one would be calculating only the missing information packets . As opposed to (4), this can be accomplished using the reduced system of equations given by:

where and is the received parity packet after substituting properly for the received information packets excluded from the recovery. Essentially, can be any square submatrix of . When is a square matrix, the number of individual submatrices is calculated using the following:

The subsystem of equations in (4) or (9) always has a unique solution, or simply is invertible, because of the geometric progression nature in each row of the Vandermonde matrix when the elements are the shift operators. Even though this is not a formal proof for the invertibility of , we verified this, by simulation, for a large set of parameters and [4].

In this section, we present a two-step efficient implementation for recovering the lost packets or equivalently finding in (9). At the receiver side, from (9), we get:

where is the adjoint matrix of , which is the transpose of the minors of since the cofactor matrix equals the minors matrix in the binary field. To find , the must be found first, multiplied by , and then the result is divided by . A basis for the proposed two-step procedure to find is an equivalent representation of (11) written as:

Therefore, the first step in finding is to solve the LHS of (12) which is essentially finding the efficiently. Since the elements of the adjoint matrix are polynomials (shifts) with coefficients from the binary field, it is not that complex to calculate the LHS of (12). The RHS of (12) dictates that the result obtained from the LHS is multiplied by . Therefore, the second step in finding is to extract efficiently from the result in the first step.

Next, we will show how to find the adj and which comprise the matrix inverse and then how to extract .

4.1. Efficient Calculation of Matrix Inverse

The most expensive operation in the recovery of is to find the determinant and the adjoint matrix of which is any submatrix of . As explained in Section 2, the elements of the adjoint matrix can be found using the determinants of the submatrices of . Therefore, finding a way to calculate the determinants results in computing the inverse. Although the original Vandermonde matrix has a known formula to find its determinant and its adjoint matrix, most of the submatrices are no longer Vandermonde matrices and such formulas donot apply to them. We present an efficient way to find the inverse of any submatrix of . This method arises because our elements in the Vandermonde matrix are monomials (single term polynomials) representing shifts. Therefore, we are actually interested in the powers of the elements in the designed matrix and submatrices. We demonstrate the principle for calculating underlying matrices inverse in the case of . By applying the logarithmic operator to each element of and removing the common factor , we get the required shifts (monomials order representation) as follows:

To find the required determinants, we apply the permutation technique [16]: write down all permutations of , denoted by of cardinality , where ! represents factorial operator and take each permutation as the subscripts of the letters which are the rows of the matrix and sum with signs determined by , where is the number of permutation inversions in . However, we donot need the permutation inversions since in the binary field the digits or are both . For example, with , the permutations and the number of inversions they contain are , , , , , and , so the determinant of is which is equivalent to in the binary field. When working with matrices of monomial elements, after applying the logarithmic operator, the determinant of the resultant powers can be represented:

where represents the logarithmic value of . Therefore, the determinant of (13) can be calculated in a simplified way as in (14). This simplified procedure can be used to calculate the determinant of any square matrix. The routine in Algorithm 1 illustrates how to find the adjoint matrix using the determinant technique in (14) for any Vandermonde submatrix.

Algorithm 1:A routine to find the adjoint matrix using the permutation technique.

Given

 G^L ; The LL matrix of interest

Find

 (G^L ) ^' ; The submatrix transponse

 P _r ; The permutations of (1, … , L) for (G^L ) ^'

Then

 For the adjoint element in location (i, j) of (G^L ) ^'

  Construct the (L1)(L1) matrix by deleting row i and column j

  Find the determinant using then technique that uses P _r

  The numbers with even multiples are canceled out

  The numbers with odd multiple stay

End

4.2. Extracting the Information from the Information Modified by the Determinant

After obtaining adj and , we can calculate the LHS of (12). By doing that, we will obtain the matrix with its rows dependent only on the corresponding rows of . This dependence implies shifts and additions determined by the . To be able to find the , we modify the condition that we pad the information packets with zeros into padding with the maximum degree of the determinant in the set of all Vandermonde submatrices, denoted by . This padding is actually greater than the original padding since . However, it will not further decrease the effective rate of the code since this extra padding can be done at the receiver side. Each unknown packet in is found by sequential bit by bit recovery within this packet by removing the effect of the previously found bit as shown in Algorithm 2 [4].

Algorithm 2:A routine to extract from the product of with .

Given

 G^L ; The LL matrix of interest

 M^S ;M^S =G^L·M^L whereM^L is unknown

 M_i^S ; The packet at row inM^S

 M_i ; The packet at row inM^L

 p _s ; The packet size after padding with g _max

Find

 ; The vector of the powers ofG^Lin ascending order

Then

 For m1: ps

  For k2: length (g)

   Factorg(k)g()

   J1modulus(m1, ps)

   J2modulus(Factorm1, ps)

    M_i^S (1, J2+1)x or (M_i^S (1, J11),M_i^S (1, J2+1))

  End

 End

M_iCyclically shift to the leftM_i^S with g()

The examples in Section 5.1 will clarify further the proposed techniques in Sections 4.1 and 4.2.

In this section, we discuss some specific cases for the design of erasure codes proposed in this paper. We demonstrate the PLR reduction capability of these codes through analytical calculations and simulation results for different code parameters.

5.1. Erasure Code Design

At the receiver side, we need to find the inverse of any submatrix of where . When we receive only the parity packets, we need to find which is given by:

The elements of the adjoint matrix as given in the RHS of (15) can be found by running the algorithm described previously. In this algorithm, in Step I, we apply the logarithmic operator of the matrix and remove the common factor , while in Step II we calculate the determinants with polynomial powers represented in parenthesis as follows:

For example, the element is found by calculating the determinant after crossing the first row and the first column of and then applying (14) but for the resulting matrix. It is . To find the determinant which is the denominator polynomial in (15), we gather the elements of any row or any column of the adjoint matrix after adding to them their corresponding original powers (shifts) which appear in the middle term in (16). Then, any number (including zero) with even multiples is canceled out and any number (including zero) with odd multiples stays because we operate in the binary field. For example, by considering the second row in the RHS of (16), we add to the elements their corresponding powers which are , , and , respectively, and then we gather them to be . Then, and are canceled out because they have even multiples, and and stay because they have odd multiples. This results in which is the power of the determinant shown in the denominator polynomial in (15). By applying this principle, any submatrix can be inverted by simple additions only.

The choice for the parameters of the proposed code is quite flexible. For example, we can design the code having a rate of 2/5. By receiving any two packets, we can recover the remaining three packets. Another example is the code having a rate of 3/5. By receiving any three packets, we can recover the remaining two packets.

5.2. Simulation Results

This section shows post decoding packet loss recovery performance, , of the proposed codes for a wide range of raw PLR in the network. As discussed earlier, we assume that we either receive the bits/packets correctly or they are missing (in doubt).

The presented results are obtained through the simulations of the actual encoding, network packet loss and decoding processes. The PLR recovery simulation results are plotted using continuous unmarked lines in all figures in this section. For comparison purposes, we also plot the theoretical curves using continuous marked lines based on the following formula [6]:

where represents the raw PLR. The PLR performance is independent of the actual packet length; however the latter determines the percentage of overhead related to padding the packets to the desired length determined by . Also, since the performance of the designed codes is characterized by the minimum distance, it is not necessary to compare it with the performance of other codes.

Figure 1 shows the PLR performance for three codes with the same minimum distance of three and the same packet size of bits but different code rates. The three codes have the parameters , , and . The rates of these codes are 2/4, 5/7, and 12/14, respectively. We can observe that the performance improves as the code rate decreases because the codes can recover two packets in a group of coded packets where .

Figure 2 shows the PLR performance for three codes with different minimum distances and different rates. The three codes have the parameters , , and . The rates of these codes are , , and , while the minimum distances are , , and , respectively. We can observe that the performance improves as the code rate decreases because they can recover , , and packets, respectively. We can observe also that the theoretical PLR performances as given by (17) agree with the simulation results.

In this section, two modifications are introduced in order to lower the amount of zero padding needed. In the first modification, the shift elements are chosen and positioned in the parity matrix such that the determinant of the new matrix , replacing , has a lower degree. A lower degree determinant implies less zero padding for the packets and hence a reduced overall overhead. The new parity matrix is such that all its submatrices are invertible. We show some of the matrix designs for a number of different sizes. We prove that the new designed matrices and their submatrices are invertible by finding the inverses using simulations. Also, the maximum degree determinant is calculated for . A comparison to the same size Vandermonde-based designs is shown.

6.1. Various Sizes Matrix Designs

The best design found that satisfy the invertibility condition using exhaustive search for the matrix is

The matrix in (18) is a nonVandermonde matrix. The invertibility of this matrix and its submatrices is proven by using brute force simulations. This is done by finding all the submatrices of (18) and calculating the determinants of these submatrices. For this matrix, we found inverses for one matrix, nine submatrices, and nine submatrices. The number of submatrices that have inverses complies with the maximum number in (10), meaning that the design is invertible for any submatrix. This design has a maximum degree determinant of four compared to its corresponding Vandermonde matrix design which has a maximum degree determinant of five.

The two designs

are good candidates for the parity coefficient matrices of sizes and , respectively. These two matrices are nonVandermonde matrices and invertible. The design has a maximum degree determinant of compared to its corresponding Vandermonde matrix design, which has a maximum degree determinant of . The design has a maximum degree determinant of compared to its corresponding Vandermonde matrix design, which has a maximum degree determinant of .

For the matrix, the best design found is given by

The matrix in (20) is also a nonVandermonde matrix. For each square size matrix, Table 1 shows the number of submatrices, the maximum degree determinant among them, and a comparison with the corresponding same size Vandermonde design. The number of submatrices having inverses complies with the maximum number in (10). This design has a maximum degree determinant of compared to its corresponding Vandermonde matrix design, which has a maximum degree determinant of .

Higher dimension matrices can also be designed and found in the same manner by generating the elements of the required size matrix and then testing the invertibility of each submatrix using brute force simulation.

The second modification that also will reduce the amount of zero padding is to zero pad with the maximum shift in the designed matrix, not with the maximum degree of the determinant. At the encoder side, each packet will be padded with the maximum shift in the matrix. Then at the receiver side, before starting decoding, the received packets are extra padded with zeros to make the total number of zero padding equal to the maximum degree determinant. This reduces the amount of overhead in the transmitted packets. This modification applies for any design (Vandermonde or nonVandermonde), and the advantages benefit equally both modifications. For example, for a Vandermonde matrix, zeros are needed originally, while only zeros are needed if we adopt the second modification, since the maximum shift in the Vandermonde matrix design is . For a nonVandermonde matrix, zeros are needed originally, while only zeros are needed if we adopt the second modification, since the maximum shift in the nonVandermonde matrix design in (20) is .

6.2. Simulation Results

This section shows post decoding packet loss recovery performance, , of the modified nonVandermonde codes for a wide range of raw PLR in the network. For comparison purposes, the performance of the corresponding Vandermonde based designs are also plotted.

Figure 3 shows the PLR performance for five codes with different minimum distances, but the same code rate of 1/2 and the same packet size of 1000 bits. The five codes have the parameters , Vandermonde-based, nonVandermonde based (Modified), Vandermonde-based, and nonVandermonde based (Modified). The minimum distances are , , and , respectively. By receiving any packets, each code can recover the remaining packets. As the channel condition improves, the code with higher parameters outperforms the others since it can recover more packets. This is the reason that the performance improves as the minimum distance of the code increases. Also, we observe that the modified designs (nonVandermonde) and the original designs (Vandermonde) have identical performances.

In this section, the general error correction capability and the decoding process using the designed codes are presented. An error decoding technique capable of correcting a single erroneous packet irrespective of the number of errors in this packet is presented. We demonstrate the packet error rate (PER) reduction capability of these codes based on the proposed error decoding technique through analytical calculations and simulation results for different code parameters.

We assume here that there is no packet loss. Therefore, at the receiver, all the coded packets are received. From the received packets arranged row-wise in a matrix , we have to infer first which packet(s) is(are) in error, and then, within this(these) packet(s), where the error locations are and their values. For binary codes considered in this paper, the error values are not required, since by knowing their positions, one just flips them. There are many procedures that could correct for errors by observing . A typical way is to use syndrome decoding which proceeds by finding the parity check matrix . The parity check matrix, , of in (7) is the matrix given by

where is the transpose of . Accordingly, the multiplication of the two partitioned matrices, and gives the zero matrix.

Now assume that the coded packets arranged in are transmitted and they are corrupted by errors. The received packets can be viewed as the coded packet corrupted (modulo- added) with packets having 1's in the error locations. These packets are referred to as error packets and are arranged row-wise in , where the latter is a column vector consisting of the elements , . The received packets arranged in the matrix are given by

where is a column vector consisting of the received packet . By pre-multiplying (22) by , one gets the packet syndrome denoted by as follows:

If , we have the indication that there were errors during the transmission. It is observed that this syndrome decoding technique in (23) depends only on the error patterns, , but not on the transmitted coded packets, . The syndrome decoding technique enables the code to correct for packet(s) irrespective of the number of bits in error inside the packet(s). A packet is considered in error if at least one bit of the packet is in error.

We show next how the syndrome decoding is utilized to correct a single erroneous packet in a group of received packets. Extending the technique to correct for more erroneous packets needs further study and is beyond the scope of this paper.

For the MDS codes capable of correcting single erroneous packet out of packets, ; that is, and thus . Now we pre-multiply the resultant syndrome equation in (23) by the matrix , which is the column-wise reverse of [4]. We call the resultant matrix, the error locator matrix , which is given as follows:

where

and represents column-reversed matrix. By substituting (25) in (24), one gets (26):

where represents row-reversed matrix. By carrying out the calculation in (26), one gets (27)

From (27), we observe that the diagonal elements of are zeros. This means that if all the error packets are zeros except one error packet , the only all-zero row in will be the row , where . Also, we notice that corresponds to the last row in the error locator matrix . This is true except for the last one , in which case any row in the error locator matrix is the error packet.

We would like to mention that the above technique needs more careful processing to handle the scenario that the error packet and a shifted version of it produce the same packet such as the all-ones error packet. Although the occurrence of such scenario is extremely small, especially for long packets, it can be handled by padding the packets resulting from the syndrome equation with zeros and then discarding these zeros when finding the error packet. These zeros are not counted as an overhead since they are padded at the receiver side.

7.1. Error Correction Designs

In this section, we discuss some specific cases for the design of packet-level error correction codes proposed in this paper. First, we consider the systematic code and present the decoding process without using , and then we demonstrate the benefits of error locator matrix in this example. This code is capable of correcting one packet in error out of the received four packets. The generator and the parity check matrices are and , respectively. At the receiver side, the decoding process starts by applying the syndrome decoding in (23) to get the following:

From (28), if the error occurs in the first received packet , the only packet that is not all-zero is while . Therefore, the two packets comprising the syndrome matrix , in (28), are identical and are the error packet, , itself. To correct the erroneous packet , one adds to it one of the packets obtained from the syndrome calculation. If the error occurs in the second received packet , the second packet of the syndrome is a shifted version by one of the first packet in the syndrome. To correct the erroneous packet , add it to the first packet of the syndrome matrix. If the error occurs in the third received packet , the second packet of the syndrome is the all-zero packet, while the first packet in the syndrome is the error packet . To correct the erroneous packet , add to it the first packet of the syndrome matrix. If the error occurs in the fourth received packet , the second packet of the syndrome is the error packet while the first packet is the all-zero packet. To correct the erroneous packet , add it to the second packet of the syndrome matrix.

The above correction can be done more efficiently by finding the error locator matrix using (24). By pre-multiplying the resultant syndrome equation in (28) by , is found to be

The above error locator matrix reduces to the first, second, third, or fourth column in Table 2 when the packet in error is the first, second, third, or fourth one, respectively. For example, if the packet in error is the fourth received packet , will be nonzero packet while . Therefore, based on (29), reduces to the fourth column in Table 2. This means that if we get with the last row comprised of all-zeros, we decide that the erroneous packet is the fourth one. In this case, can be taken either as the first, second, or third packet in the fourth column of . When the packet in error is the first, second, or third one, we notice as before that the zero in the error locator matrix indicates the location of the packet in error and the error packet can be taken as the last packet in the error locator matrix in Table 2.

The systematic code is capable of correcting one packet in error out of the received five packets. By following the procedure from (26), the error locator matrix for this code is as follows:

The above error locator matrix reduces to the first, second, third, fourth, or fifth column in Table 3 when the packet in error is the first, second, third, fourth, or fifth one, respectively, in a block of received packets. We notice as before that the zero in the error locator matrix indicates the location of the packet in error. Also, the error packet that should be added to correct the erroneous packet is the last row in the error locator matrix. This is true except when the last received packet is in error, in which case any row in the error locator matrix is the error packet.

We discussed two codes and which are both single error correcting code like the Hamming code. However, the rates of these three codes are 35/70, 42/70, and 40/70, respectively. The decoding process for the first code is simple, but the code has a rate of . The decoding process of the second code is a little bit more involved compared to the first one, but the code has a higher rate of . Higher rate single error correcting codes can be designed, but the decoding complexity increases slightly as the code rate increases.

We presented an efficient decoding algorithm to correct a single erroneous packet in a family of codes having a minimum distance of three. Therefore, this family is capable of correcting all bits in error within a single erroneous packet, irrespective of the size of the packet. The family has the parameters , where . The rate of this family is . This designed family has more flexible code parameters when compared to the family of Hamming codes having the parameters , where . The next Hamming code after the is the which has a code rate of . A comparable code performance in our design is when taking to construct the code having a code rate of . However, the latter is less complex since it has a code length of , which is almost half of the Hamming code of length . As a result, the delay in constructing the encoder and decoder matrices is greatly reduced, especially as the code rate increases.

7.2. Simulation Results

This section shows postdecoding packet error rate performance, , of the proposed codes for a wide range of raw PER in the network.

The presented results are obtained through the simulations of the actual encoding, network packet error and decoding processes. The PER recovery simulation results are plotted using continuous unmarked lines. For comparison purposes, we also plot the theoretical curves using continuous marked lines based on (17) but taking the summation from with instead of and representing here the raw PER.

Figure 4 shows the PER performance for three codes with the same minimum distance of three but different code rates. The three codes have the parameters , , and . The rates of these codes are 2/4, 5/7, and 12/14, respectively. We can observe that the performance improves as the code rate decreases because the codes can correct for one packet in a group of coded packets where . Also, it can be noted that the theoretical PER performances agree with the simulation results.

We summarize now the advantages of working with the proposed code design for packet-level FEC in which the elements of the Vandermonde matrix are the shift operator. The code design is applicable to recover from lost packets up to out of the coded packets, or correct one erroneous packet out of the received packets. This design is simple to implement since all our arithmetic operations are done in the binary field using only simple shifts and modulo- additions.

The only disadvantage is the overhead associated with the need to zero pad each packet with the maximum degree, , of the determinants among the set of all determinants of square submatrices of the designed Vandermonde matrix. To reduce the overhead considerably, however, we proposed modified nonVandermonde matrix designs which were found by exhaustive search. We believe that finding such designs in more structured way is still a challenging problem especially as the matrix size increases. To even further reduce this overhead in both designs, we can only zero pad with the maximum shift in the matrix which is much less than .

The overhead reduces the efficiency of the design (overall code rate) especially when designing for large code parameters. However, as the packets size increases, the efficiency improves. Therefore, the design is applicable to packets of any size provided that they are not very small. For moderate code parameters, packets of few hundred bits (all network standards requires even more than this) are good enough that will not affect the efficiency of the code very much. For large code parameters, the efficiency can be improved by increasing the packet size and/or by utilizing the mentioned ways of reducing the overhead.

For erasure recovery, we showed how to find the inverse of a matrix using a simple algorithm by exploiting the logarithmic operator of the elements of the Vandermonde matrix and converting the operations to simple modulo- additions. For error correction, we presented a syndrome decoding algorithm that corrects for a single erroneous packet using a specialized error locator matrix. The design is suitable for real-time applications and multicasting, where conventional ARQ protocols employing retransmission are inadequate, due to the introduction of delay and jitter. Also, the design can be exploited in cross-layer protocols design to recover from both erasures and errors simultaneously.

The authors acknowledge the support of King Fahd University of Petroleum and Minerals (KFUPM).

1. DJ Costello, J Hagenauer, H Imai, SB Wicker, Applications of error-control coding. IEEE Transactions on Information Theory 44(6), 2531–2560 (1998). Publisher Full Text

2. MG Luby, M Mitzenmacher, MA Shokrollahi, DA Spielman, Efficient erasure correcting codes. IEEE Transactions on Information Theory 47(2), 569–584 (2001). Publisher Full Text

3. S Karande, H Radha, Partial Reed Solomon codes for erasure channels. Proceedings of the IEEE Information Theory Workshop (ITW '03), April 2003, 82–85

4. A Al-Shaikhi, in Innovative designs and deplyments of erasure codes in communication systems, Ph, ed. by . D. dissertation (Dalhousie University, Nova Scotia, Canada, 2007)

5. RL Collins, JS Plank, Assessing the performance of erasure codes in the wide-area. Proceedings of the International Conference on Dependable Systems and Networks (DSN '05), June 2005, Yokohama, Japan, 182–187

6. S Lin, DJ Costello, Error Control Coding (Prentice-Hall, Upper Saddle River, NJ, USA, 2004)

7. SS Karande, H Radha, The utility of hybrid error-erasure LDPC (HEEL) codes for wireless multimedia. Proceedings of the IEEE International Conference on Communications (ICC '05), May 2005, Seoul, South Korea 2, 1209–1213

8. A Al-Shaikhi, J Ilow, X Liao, An adaptive FEC-based packet loss recovery scheme using RZ turbo codes. Proceedings of the 5th Annual Conference on Communication Networks and Services Research (CNSR '07), May 2007, Fredericton, Canada, 263–267

9. AA Al-Shaikhi, J Ilow, Packet loss recovery codes based on Vandermonde matrices and shift operators. Proceedings of the IEEE International Symposium on Information Theory (ISIT '08), July 2008, Toronto, Canada, 1058–1062

10. FJ Ayres, Schaum's Outline of Theory and Problems of Matrices (Schaum, New York, NY, USA, 1962) PubMed Abstract | Publisher Full Text

11. A Ben-Israel, TN Greville, Generalized Inverses: Theory and Applications (Wiley Interscience, New York, NY, USA, 1977)

12. DS Dummit, RM Foote, Abstract Algebra (Prentice-Hall, Englewood Cliffs, NJ, USA, 1998)

13. J Lacan, J Fimes, Systematic MDS erasure codes based on Vandermonde matrices. IEEE Communications Letters 8(9), 570–572 (2004). Publisher Full Text

14. J Fimes, J Lacan, et al. Estimation of the number of singular square submatrices of Vandermonde matrices defined over a finite field (ENSICA, January 2003)

15. F MacWilliams, N Sloane, The Theory of Error-Correcting Codes (North Holland, Amsterdam, The Netherlands, 1978)

16. T Muir, Treatise on the Theory of Determinants (Dover Phoenix Editions, New York, NY, USA, 1960)