TY - JOUR

T1 - A systolic array implementation of the Feng-Rao algorithm

AU - Liu, Chih-Wei

AU - Huang, Kuo Tai

AU - Lu, Chung Chin

PY - 1999/7/1

Y1 - 1999/7/1

N2 - 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 concurrency of the Feng-Rao algorithm can be achieved. The time complexity of the proposed architecture is m + g + 1 by using a series of t + ⌊g-1/2⌋ + 1, nonhomogeneous but regular, effective processors, called PE cells, and g trivial processors, called D cells, where t is designed as the half of the Feng-Rao bound. Each D cell contains only delay units, while each PE cell contains one finite-field inverter and, except the first one, one or more finite-field multipliers. Cell functions of each PE cell are basically the same and the overall control circuit of the proposed array is quite simple. The proposed architecture requires, in total, t + ⌊g-1/2⌋ + 1 finite-field inverters and (t+⌊(g-1)/2⌋)(t+⌊(g-1)/2⌋+1)/2 finite-field multipliers. For a practical design, this hardware complexity is acceptable.

AB - 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 concurrency of the Feng-Rao algorithm can be achieved. The time complexity of the proposed architecture is m + g + 1 by using a series of t + ⌊g-1/2⌋ + 1, nonhomogeneous but regular, effective processors, called PE cells, and g trivial processors, called D cells, where t is designed as the half of the Feng-Rao bound. Each D cell contains only delay units, while each PE cell contains one finite-field inverter and, except the first one, one or more finite-field multipliers. Cell functions of each PE cell are basically the same and the overall control circuit of the proposed array is quite simple. The proposed architecture requires, in total, t + ⌊g-1/2⌋ + 1 finite-field inverters and (t+⌊(g-1)/2⌋)(t+⌊(g-1)/2⌋+1)/2 finite-field multipliers. For a practical design, this hardware complexity is acceptable.

KW - Algebraic-geometric codes

KW - Error-correcting codes

KW - Feng-rao algorithm

KW - Systolic array

UR - http://www.scopus.com/inward/record.url?scp=0032592915&partnerID=8YFLogxK

U2 - 10.1109/12.780877

DO - 10.1109/12.780877

M3 - Article

AN - SCOPUS:0032592915

VL - 48

SP - 690

EP - 706

JO - IEEE Transactions on Computers

JF - IEEE Transactions on Computers

SN - 0018-9340

IS - 7

ER -