M-Sequences and Dual Bases Over GF(q/sup m/)
John Joseph Komo, W.J. Reid · 2005
An m-sequence over GF(q/sup m/) can be expressed as a vector of m-sequences whose component m-sequences are shifted versions of an m-sequence over GF(q). The amount of shift between components of the m-sequence over GF(q/sup m/) is given as a ratio of elements of the trace dual basis corresponding to the basis expressing GF(q/sup m/) over GF(q). An efficient algorithm, which does not require evaluation of the trace, is developed for obtaining the ratio of trace dual basis elements to the first element. The dual basis can then be completely obtained by evaluating the first dual basis element. Another algorithm is developed which efficiently evaluates this first element. Included in this algorithm is a sequential evaluation of the trace which can be sequentially obtained directly in terms of the coefficients of the primitive polynomial that generates GF(q/sup m/).