Decoding Interleaved Reed-Solomon (IRS) codes usually is good for correcting burst errors in the channel. Various decoding methods have been proposed up to now. Among all, multi-sequence shift register synthesis gives us an efficient way to decoding IRS codes jointly. In 1989, Feng and Tzeng proposed a Generalized Euclidean algorithm (GEA) and applied to solve multi-sequence shift register synthesis problem.

However, the algorithm from Feng and Tzeng can only be applied when RS codes are homogeneous. Regarding decoding heterogeneous IRS codes, Zeh et.al in 2010 reformulated sequences of different lengths to same lengths by increasing the interleaving factor. Later, Kampf et.al modified the FengTzeng's Euclidean algorithm and applied it for decoding heterogeneous IRS codes without any reformulation.

In our work, the modification of generalized Euclidean algorithm will be accelerated by the idea of "divide and conquer".