An algorithm for shifted continued fraction expansions in parallel linear time

✍ Scribed by Harald Niederreiter; Michael Vielhaber

• Publisher: Elsevier Science
• Year: 1999
• Tongue: English
• Weight: 119 KB
• Volume: 226
• Category: Article
• ISSN: 0304-3975
• DOI: 10.1016/s0304-3975(99)00067-5

✦ Synopsis

The linear complexity proÿle of a sequence of length n is readily obtained in O(n 2 ) steps by the Berlekamp-Massey algorithm (BMA). Piper demands that the linear complexity proÿles should be acceptable for every starting point, that is, for all shifted sequences as well. By repetition of the BMA, this can be veriÿed in O(n 3 ) steps.

This paper describes a transducer that in only Cq• n+1 2 Fq operations, where C2 = 7 and Cq = 6:5 for q¿3, computes the continued fraction expansions of all n shifted sequences (a1; : : : ; an); (a2; : : : ; an), to (an). Hence, no additional computational e ort is necessary to check Piper's demand. When n transducers are occupied in parallel, the output is obtained in Cq Fq operations per symbol, that is, in parallel linear time, yielding an O(n 2 • log n) time-space product.