Folding large regular computational graphs onto smaller processor arrays
Kevin J. Page, Paul M. Chau · Proceedings of SPIE, the International Society for Optical Engineering/Proceedings of SPIE · 1996
Index Mapping is a novel approach to mapping a class of algorithms onto linear permutation networks such as the shuffle graph. This class includes the Viterbi Algorithm, the Fast Fourier Transform, and the Bitonic Sort, among others. With this technique, it is possible to analyze a large number of possible partitioning and scheduling schemes and choose for a given technology the optimum implementation. This technique will be demonstrated by two mappings of a variable and large constraint length Viterbi decoder onto a smaller fixed interconnection processing network with minimum hardware resources. The hardware built for this mapping can calculate the Viterbi algorithm for any constraint length from 3 to 15 with programmable code polynomials and code rates from 1/2 to 1/6.