LPC and Sparse LPC Algorithms and RTL Architecture
Author
Pedersen, Henrik Holbæk
Term
4. term
Education
Publication year
2015
Abstract
Dette projekt undersøger linear prediction coding (LPC) og sparsomme lineære prædiktionsalgoritmer med det formål at udvikle en hardwarearkitektur på Register Transfer Level (RTL), dvs. et designniveau hvor data bevæger sig mellem registre og operationer. Vi foreslår to algoritmer til at beregne henholdsvis lineære prædiktionskoefficienter og sparsomme prædiktionskoefficienter og analyserer deres forløb og indbyggede parallelisme. På baggrund af analysen opbygges en finit tilstandsautomat med datapath, bestående af en kontrolsti og en datasti. Kontrolstien beskrives med algorithmic state machine (ASM) diagrammer, og datastien sammensættes af hardwareblokke. Den sparsomme prædiktionsalgoritme, som analyseres, er en ny idé fremlagt af vejleder Tobias Lindstrøm Jensen, og derfor behandles den indgående. Algoritmen kører fire iterationer, hvor der i hver iteration løses et least squares-problem på højresiden, dvs. en bedste-tilpasning af ligningerne. I denne sammenhæng peger analysen på, at Levinson-algoritmen er den mest hensigtsmæssige metode til at finde løsningen, selvom andre metoder også undersøges. Arbejdet munder ud i to arkitekturer, som kan implementeres i VHDL eller videreudvikles med forskellige optimeringsmetoder.
This project examines linear prediction coding (LPC) and sparse linear prediction algorithms with the goal of developing a Register Transfer Level (RTL) hardware architecture, that is, a design level describing how data moves between registers and operations. We propose two algorithms to compute linear prediction coefficients and sparse prediction coefficients, and we analyze their execution flow and inherent parallelism. Based on this analysis, we build a finite state machine with a datapath, composed of a control path and a data path. The control path is specified using algorithmic state machine (ASM) charts, and the data path is assembled from hardware blocks. The sparse prediction algorithm studied is a novel idea recently presented by the supervisor, Tobias Lindstrøm Jensen, and is therefore examined in depth. The algorithm runs four iterations, each solving a right-hand-side least-squares problem, i.e., finding a best-fit solution to the equations. In this setting, our analysis indicates that the Levinson algorithm is the most suitable way to obtain the solution, although other methods are also considered. The work concludes with two architectures that can be implemented in VHDL or further improved using various optimization methods.
[This abstract was generated with the help of AI]
Keywords
Documents