Title:
Speedup an FSM by Non-linear Lookahead and its Application in Huffman
Decoding


Students:
JinJun Xiong   and   Fei Li


Astract:


Lookahead is an efficient way to reduce the iteration bound. Many hardware
implementations of DSP algorithms use lookahead as a method to increase
the throughput. Since most DSP algorithms are linear algorithms, the
linear lookahead has been widely studied and can be performed using
formalized method such as state space lookahead. However, when we apply lookahead to a general non-linear algorithm or an FSM, it becomes non-linear lookahead. People have been working on the speedup of a general FSM using ad hoc techniques.


In this project, we would like to investigate all these ad hoc techniques
and try to give non-linear lookahead a formal representation. With our
formal method, any general FSM can be implemented with an arbitrary execution speed and reasonable hardware complexity. The major contribution of this project is that our formal method applies lookahead algorithm transformation to any non-linear algorithm and the transformed algorithm can be implemented at an arbitrary clock rate. A simple alternate mark inversion (AMI) line coder will be implemented in Verilog using our method to verify the proposed formal method.


Later, we would like to apply our formal method of non-linear lookahead
transformation to the Huffman Decoding. Huffman decoding is frequently used for images, video and other applications. Due to the recursion whithin the reconstructing algorithm in Huffman Decoding, the throughput for a target IC technology is limited. We will show that, by applying the formal non-linear lookahead transformation, unlimited throughput may be obtained.


[1] "Designing High-Throughput VLC Decoder Part I - Concurrent VLSI
Architectures",
Shih-Fu Chang and David G. Messerschmitt.


[2] "Designing High-Throughput VLC Decoder Part II - Parallel Decoding
Methods",
Horng-Dar Lin and David Messerschmitt.