## 2 Background
### Overview of Progressive Network Coding  
A variety of decoding methods that employ the random linear network coding technique is based on matrix inversion algorithms [29, 30]. Though using the traditional algorithms is a proven method of parallel decoding in network environments, there is an additional cost incurred from network transmission delay. As the system must wait until all packets are received to compose the matrices used in the aforementioned traditional decoding algorithms, this delay is particularly problematic. As such, we can obtain greater performance using progressive decoding in packet switching network environments, which are subject to these transmission delays.  
The traditional matrix inversion algorithms require a complete matrix to perform the decoding operation; this results in additional delays due to the waiting period. In contrast, progressive decoding requires only one row of the matrix to proceed with decoding. As such, progressive decoding is more suitable to network environments that are subject to long transmission delays.  
The decoding process for traditional matrix inversion algorithms can be expressed with a computational complexity of \(O(n^{3})\), after the last row has arrived. However, with the progressive decoding we can initiate the decoding process when as each row is received. Since we have already finished computation of all prior rows, the most recent row can be processed with complexity of \(O(n^{2})\). In our evaluation, we employs progressive decoding to implement parallel decoding algorithms on the Cell BE.  
[PERSON] and [PERSON] were the first to demonstrate the effectiveness of parallelization in network coding with their _Progressive Parallelized Network Coding_ algorithms [28]. However, our previous research has identified inefficiencies and unbalancing in their work, particularly with respect to large coefficient matrix sizes and has proposed Dynamic Vertical Partitioning (DVP) algorithm [31]. We employ the DVP algorithm here for the Cell BE system, and suggest enhancements, which require a balanced workload implementation, across the heterogeneous multi-core processor.  
Figure 5 presents the specific operations of progressive decoding, from _Stage A_ to _Stage E_ and Table 1, which introduced in [28] shows description of the operations and percentage of each operation step. In fact, Figure 5 depicts a decoding process after operations on the \((k-1)_{th}\)'s row has just been finished and the \(k_{th}\) row just arrives at the destination node.  
Figure 5(a) depicts the operations at _Stage A_; the decoding process begins in the second figure within Figure 5(a). At the beginning, the first row is multiplied with the first element of the arriving row, and the resulting row is subtracted from the arriving row. The same operations are  
row; it is multiplied with the second element of the arriving row and the resultant row is subtracted from the arriving row. These operations are continued until all leading values are reduced to \"0\".  
After the operations of _Stage A_ are finished, the next decoding process identifies the first non-zero coefficient element (_Stage B_). It then determines whether the new row is linearly independent of the previously received rows (_Stage C_). The newly arriving row is then divided along the first non-zero element of the row, referred to as the _pivot_ (_Stage D_) in Figure 5(b). Finally, we reduce the values of this same column across all previous rows to \"0\" (_Stage E_) depicted in Figure 5(c).