Binaire, grijze en one-hot codering vergelijken

Dit artikel toont een vergelijking van de implementaties die het resultaat zijn van het gebruik van binaire, grijze en one-hot-coderingen om state-machines in een FPGA te implementeren. Deze coderingen worden vaak geëvalueerd en toegepast door de synthese- en implementatietools, dus het is belangrijk om te weten waarom de software deze beslissingen neemt.

Eindige-toestandsmachines (FSM's) zijn een veel voorkomend onderdeel van bijna elk digitaal systeem. Dat is de reden waarom synthesetools uw code vaak inspecteren om FSM's te detecteren en optimalisaties uit te voeren die de codering van de statussen kunnen wijzigen. Het maakt niet uit of u zorgvuldig de waarden hebt geselecteerd en gespecificeerd die uw statussen in uw broncode implementeren, de synthesetool kan die waarden vervangen door andere die zelfs een andere bitlengte hebben dan uw oorspronkelijke codering.

Als je het implementeren van state-machines in Verilog wilt opfrissen, lees dan mijn artikel getiteld Creating Finite State Machines in Verilog.

Codering van staten:grijs vs. binair vs. one-hot

De drie meest populaire coderingen voor FSM-statussen zijn binair, grijs en one-hot.

Binaire codering

Binaire codering is de rechttoe rechtaan methode die u intuïtief kunt gebruiken wanneer u waarden opeenvolgend toewijst aan uw toestanden. Op deze manier gebruik je zo min mogelijk bits om je toestanden te coderen.

Een voorbeeld van one-hot codering. Afbeelding door Steve Arar

Grijze codering

Gray-code bestaat uit een reeks waarbij slechts één bit verandert tussen de ene waarde en de volgende. Naast het gebruik van het minimale aantal bits, minimaliseert deze codering het dynamische stroomverbruik als de volgorde van toestanden optimaal wordt gevolgd.

Het grijze codewiel. Afbeelding van Marie Christiano

One-hot codering

Ten slotte bestaat one-hot codering uit het gebruik van één bit dat elke toestand vertegenwoordigt, zodat op elk moment een toestand wordt gecodeerd als een 1 in het bit dat de huidige toestand vertegenwoordigt, en 0 in alle andere bits. Dit lijkt in eerste instantie misschien niet erg efficiënt vanwege het aantal gebruikte bits en het buitensporige aantal ongeldige toestanden. One-hot codering is echter erg goed in het vereenvoudigen van de stimuluslogica voor de flip-flops, omdat het niet nodig is om de toestanden te decoderen. De bits zijn de Staten.

Een voorbeeld van one-hot codering. Afbeelding door Steve Arar

Voor meer informatie over toestandscoderingen kun je het artikel Encoding the States of a Finite State Machine in VHDL door Steve Arar lezen.

Welke codering is de beste?

Dit is een lastige vraag, vooral omdat elke codering zijn voordelen en tekortkomingen heeft, dus het komt neer op een optimalisatieprobleem dat van een groot aantal factoren afhangt.

• Als een heel eenvoudig systeem zeer vergelijkbare resultaten oplevert voor alle coderingen, dan is de originele codering de beste keuze.
• Als de FSM door zijn toestanden in één pad gaat (zoals een teller), dan is Gray-code een zeer goede keuze.
• Als de FSM een willekeurige reeks toestandsovergangen heeft of naar verwachting op hoge frequenties zal werken, is one-hot codering misschien de juiste keuze.

Nu zijn al deze beweringen slechts gissingen, en het vinden van de optimale statustoewijzing is een ingewikkeld probleem. Daarom is mijn officiële advies om de samensteller voor je te laten beslissen. Dat gezegd hebbende, besloot ik de resultaten voor deze drie coderingen te vergelijken in drie verschillende ontwikkeltools en drie verschillende statusmachines.

In het volgende artikel zullen we de resultaten van mijn experimenten bespreken.