Abstrakt. Detta dokument behandlar den formella specifikationen och verifieringen av snabba Fouriertransform-algoritmer (FFT) på olika abstraktionsnivåer baserade på HOL-teorin. Vi använder oss av befintliga teorier i HOL om reella och komplexa tal, IEEE standard flytta-punkt, och fast-punkt aritmetik för att modellera FFT algoritmer. Sedan härleder vi, genom att bevisa teorem i HOL, uttryck för ansamling av avrundning fel i flytande och fast punkt FFT-konstruktioner med avseende på motsvarande ideala reella och komplexa tal specifikation. HOL-formaliseringen och bevisen anses vara i god överensstämmelse med de teoretiska pappers- och pencil motsvarigheterna. Slutligen använder vi ett klassiskt hierarkiskt bevis tillvägagångssätt i HOL för att bevisa att FFT-implementationen på registeröverföringsnivån (RTL) innebär motsvarande höga fasta punkters algoritmiska specifikation.
På liknande sätt, Akbarpour et al. REF använde HOL-teorin för formell specifikation och verifiering av en generisk FFT-algoritm.
A methodology for the formal verification of FFT algorithms in HOL
{'venue': 'FMCAD', 'journal': None, 'mag_field_of_study': ['Computer Science']}