Speed up an FSM Via Nonlinear Look-ahead Transformation & Its Application to Huffman DecodingMotivationOur ApproachExample: AMI EncoderExample: AMI Encoder (cont)Achieved and Expected ResultsSpeed up an FSM Via Nonlinear Look-ahead Transformation & Its Application to Huffman DecodingFei LiJinjun XiongUniversity of Wisconsin-MadisonMotivationFinite state machine (FSM)Most commonly used in sequential circuitsPerform non-linear recursive algorithmsProcessing rate limited by iteration boundApplications require high-throughputReal-time processingHuffman decodingNonlinear algorithm transformation techniques and concurrent architectures may be of help1ftime to compute the next stateOur ApproachNonlinear look-ahead transformationMore state transitions in one computational stepA formal transformation method using state transition matrixConcurrent block processingHigh-order look-ahead transformationHigh hardware complexityLong critical pathBlock processingExplore more concurrencyEasy to pipelineExample: AMI EncoderAlternate Mask Inversion (AMI) Encodermap a binary sequence into a bipolar pulse sequenceMaintain zero DC biasFormal representation of state transitionS(n+1) = T(n) * S(n) S(n+m) = T(n+m-1)… T(n) S(n)State indicator vectorState transformation matrix T(n)Independent of current stateEasy to perform look-aheadS 0 S 1[ 0 , 0 ][ 1 , + ][ 0 , - ][ 0 , 0 ]0110)0(T1001)1(T01)0(S10)1(SExample: AMI Encoder (cont)Look-ahead by three, assuming input string 010State Transition MatrixCurrent State 0 Current State 1Concurrent architecture w/ block processing0110)0()1()0( TTTT-10)0(STS-01)1(STSAchieved and Expected ResultsAchieved ResultsDerived formal representation of nonlinear look-ahead using state transition matrixDesigned concurrent block processing architectureMethod applied and verified on the AMI encoder design in Verilog Expected ResultsApply the method to Huffman decoderHandle the issue of variable length codeImplement it in VerilogAchieve
View Full Document
Unlocking...