A systolic array implementation of the Feng-Rao algorithm

An efficient implementation of a parallel version of the Feng-Rao algorithm on a one-dimensional systolic array is presented in this paper by adopting an extended syndrome matrix. Syndromes of the same order, lying on a slant diagonal in the extended syndrome matrix, are scheduled to be examined by a series of cells simultaneously and, therefore, a high degree of concurren cy of the Feng-Rao algorithm can be achieved. The time complexity of the pr oposed architecture is m + g + 1 by using a series of t + [g-1/2] + 1, nonh omogeneous but regular, effective processors, called PE cells, and g trivia l processors, called D cells, where t is designed as the half of the Feng-R ao bound. Each D cell contains only delay units, while each PE cell contain s one finite-field inverter and, except the first one, one or more finite-f ield multipliers. Cell functions of each PE cell are basically the same and the overall control circuit of the proposed array is quite simple. The pro posed architecture requires, in total, t + [g-1/2] + 1 finite-field inverte rs and (t+[(g-1)/2])(t+[(g-1)/2]+1)/2 finite-field multipliers. For a pract ical design, this hardware complexity is acceptable.