DOC PREVIEW
UW-Madison ECE 734 - An Algorithm to Perform Look-Ahead Transformations on Finite State Machines

This preview shows page 1-2-3-4 out of 11 pages.

Save
View full document
View full document
Premium Document
Do you want full access? Go Premium and unlock all 11 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 11 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 11 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 11 pages.
Access to all documents
Download any document
Ad free experience
Premium Document
Do you want full access? Go Premium and unlock all 11 pages.
Access to all documents
Download any document
Ad free experience

Unformatted text preview:

An Algorithm to Perform Look-Ahead Transformations on Finite State MachinesGreg AlbinECE 734: Spring 04Abstract:This paper provides an algorithm that will “unroll” a single input state diagram and transform it into a multiple input state diagram. This exploits the inherent parallelismfound in many finite state machines, specifically those that implement Huffman decoders.I. INTRODUCTIONThe Huffman code is a used in many applications including HDTV, JPEG Compression, fiber optic networks and real-time reconstruction [1]. The Huffman code is set up so that the shorter code words have alarger probability than the smaller code words. An example of a Huffman code is given in figure 1. In this code, the alphabet letter C1 will have a higher probability than C2.Alphabet CodewordC1 0C2 10C3 110C4 111Figure 1: Sample Huffman CodeMaking a Huffman encoder can easily be done by chaining together (n-1) demultiplexors where n is the maximum size of your codeword. Significant speed-up can be obtained in a Huffman encoder by adding pipelining latches between every demultiplexor. The encoder has the ability to take one alphabet character in every clock-cycle and output a code-word every clock-cycle.Designing a Huffman Decoder is not as straight-forward of a task. There are many different implementations to choose from [2]. The Huffman code is also a Variable Length Code (VLC) which means that you will not be able to get a single input and give a single output every clock cycle. Either the number of inputs will vary per clock cycle and the outputs will remain constant, or the number of outputs will vary per clock cycle while the inputs remain constant. This paper focuses on the latter implementation with a constant stream of inputs.One such implementation of the code in figure 1 is shown in figure 2 below. This takes one input every clock and will give an output on some clock cycles. Figure 2: FSM for a Single-Input Huffman Decoder [1]A Look-ahead transformation is a way to add parallelism to VLSI implantations of DSP algorithms. Usually, look-ahead transformationswork with dependence graphs and difference equations. The goal of this paper is to give a systematic method for performing look-ahead transformations on a state diagram. Although one could use recursionof Boolean equations to accomplish this, it is not very efficient for writing into software. This paper will present a method that relies on a special type of matrix multiplication.II. THE ALGORITHMOne way to think about this problem is to make a state transition matrix. Below is a state transition matrix for the finite state machine in figure 2:101010RIf an arc travels from State i to State j, this is represented by an entry in ith row and the jth column of R. The entry indicates the input value on the arc. If there is no arc for a transition, this is indicated by placing an  in the corresponding entry. Finally, if two arcs with different inputs have the same source and destination states, both inputs are put into the entry separated by a + sign. R31 is an example where two arcs with different inputs travel from state 3 to state 1.In order to perform a look-ahead, we utilize a property similar to matrix multiplication. Matrix multiplication is a convenient way to utilize a look-ahead because we have:nkkjikijrrzRRZ12This means that zij will be the two-step transition from state i to some intermediary state to state j.1101100001111000110110001010101010102ZNow to calculate the matrix Z2, we will need to modify the matrix multiply operation indicated above. The multiplication operator inside the summation indicates a non-commutative concatenation of the entries of each matrix. If either operand is equal to infinity, the result is always infinity. The summation operation is also a non-commutativeconcatenation also. If either operand is equal to infinity it is not included in the summation unless both operands are in which case theresult is infinity.Formally, we have: nkkjikijNNrrzRZ1otherwiserrrrrrkjikkjikkjik, otherwiseaaaaaaaaaaijjijijiji,Although the commutative property does not hold for either addition or multiplication the distributive property does:kjkikjiaaaaaaa  )(Next, in a similar fashion to the inputs, we map the outputs to a transition matrix similar to the R matrix above:430201SIn the S matrix, the numbers represent which output is activated on the arc. For example S21 = 1, which means that the arc starting at state 2 and ending at state 1 will activate output C2 in figure 2. Analogously to the input matrix, if there are two arcs that start and end at the same states, they will both outputs will be put in the appropriate entry separated by a plus sign. The multiplication and addition rules are exactly the same as above. So:nkkjikijNNsswSW1where scalar multiplication and addition are defined the same as above. An example calculating W2 is shown below:4030413120040321001002114302014302012WLooking at the resulting matrices for Z2 and W2 we have done a successful 2-level look-ahead on the state-transition diagram. The resulting diagram is shown in figure 3 below:Figure 3: FSM for a 2-Level Look-Ahead Huffman Decoder [1] This method is an easy to calculate by hand for the first few levels of look-ahead transformations, but would get cumbersome beyond that. When calculating by hand, one needs to be careful to preserve operand order so that the arcs in the input and output matrices matchup. III. MODIFICATIONS FOR SOFTWARE IMPLEMENTATION As convenient as the method in part II is for calculating by hand, it is rather cumbersome to map to a software algorithm. The two-dimensional matrix multiply operations turn out to be three-dimensional array operations, so it is advantageous to modify the algorithm a bit to fit better with software storage space. Instead of putting multiple arcs of the state diagram into a single entry of a two-dimension matrix, the


View Full Document

UW-Madison ECE 734 - An Algorithm to Perform Look-Ahead Transformations on Finite State Machines

Documents in this Course
Load more
Download An Algorithm to Perform Look-Ahead Transformations on Finite State Machines
Our administrator received your request to download this document. We will send you the file to your email shortly.
Loading Unlocking...
Login

Join to view An Algorithm to Perform Look-Ahead Transformations on Finite State Machines and access 3M+ class-specific study document.

or
We will never post anything without your permission.
Don't have an account?
Sign Up

Join to view An Algorithm to Perform Look-Ahead Transformations on Finite State Machines 2 2 and access 3M+ class-specific study document.

or

By creating an account you agree to our Privacy Policy and Terms Of Use

Already a member?