Look-ahead in dynamic programming and quantizer loops

Research output: Contribution to journalConference articlepeer-review

14 Scopus citations

Abstract

The add-compare-select (ACS) loop operation in serial dynamic programming (DP) problems inherently limits the speed or the iteration period. The author shows that the ACS loop operation (although nonlinear) can exploit look-ahead. He uses techniques of look-ahead, decomposition, and incremental computation, and proposes fine-grain pipelined and parallel architectures for area-efficient high-speed VLSI implementation of DP problems. The word-level arithmetic implementation complexity of the architecture is proportional to the cube of the number of states of the DP problem, logarithmic in number of loop pipeline levels, linear in block size, and additive with respect to pipelining and block processing. The data-dependent nature of the quantization operation limits the opportunities to pipeline the quantizer loops. The author proposes an approach to transform the quantizer loop into an equivalent form that can exploit look-ahead. The transformed quantizer loop recursion is shown to be similar to the DP recursion, and variations of the DP processor architectures can be used for high-speed implementation of simple quantizer loops.

Original languageEnglish (US)
Pages (from-to)1382-1387
Number of pages6
JournalProceedings - IEEE International Symposium on Circuits and Systems
Volume2
StatePublished - 1989
EventIEEE International Symposium on Circuits and Systems 1989, the 22nd ISCAS. Part 1 - Portland, OR, USA
Duration: May 8 1989May 11 1989

Fingerprint

Dive into the research topics of 'Look-ahead in dynamic programming and quantizer loops'. Together they form a unique fingerprint.

Cite this