State encoding for low power

Last updated October 22, 2024

State encoding assigns a unique pattern of ones and zeros to each defined state of a finite-state machine (FSM). Traditionally, design criteria for FSM synthesis were speed, area, or both. Following Moore's law, with technology advancement, density and speed of integrated circuits have increased exponentially. With this, power dissipation per area has inevitably increased, which has forced designers for portable computing devices and high-speed processors to consider power dissipation as a critical parameter during design consideration.^[1]^[2]

Background

Synthesis of FSM involves three major steps:

State minimization: As the name suggests, the number of states required to represent FSM is minimized. Various techniques and algorithms like implication tables, row matching, and successive partitioning identify and remove equivalent or redundant states.
State assignment or encoding involves choosing boolean representations of the internal states of FSM. In other words, it assigns a unique binary code to each state. Selection of the right encoding technique is critical, since a wrong decision may result in an FSM that uses too much logic area, is too slow, consumes too much power, or any combination of these.
Combinational logic minimization uses unassigned state-codes as don't-care states in order to reduce the combinational logic.

Existing encoding techniques

Following are some of the techniques which are widely used for state encoding:

In one-hot encoding , only one of the bits of the state variable is "1" (hot) for any given state. All the other bits are "0". The Hamming distance of this technique is 2. One-hot encoding requires one flip-flop for every state in the FSM. As a result, the state machine is already "decoded," so the state of the machine is determined simply by finding out which flip-flop is active. This encoding technique reduces the width of the combinational logic, and as a result, the state machine requires fewer levels of logic between registers, reducing its complexity and increasing its speed.
In binary encoding, the number of bits ( $b$ ) per state depends on number of states ( $n$ ). The relationship is defined by the equation $b = log 2 (n)$ . In this technique, the states are assigned in a binary sequence where the states are numbered starting from 0 and up. The number of flip-flops used is equal to the number bits ( $b$ ). Since binary encoding uses the minimum number of bits (flip-flops) to encode a machine, the flip-flops are maximally utilized. As a result, more combinational logic is required to decode each state when compared to one-hot encoding. Binary encoding requires fewer flip-flops when compared to one-hot encoding, but Hamming distances can be as worse—up to the number of bits ( $b$ ).

In Gray encoding , also known as reflected binary encoding, states are assigned so that consecutive state codes differ by only one bit. In this encoding, the relationship between number of bits and the number of states is defined by $b = log 2 (n)$ . The number of flips-flops used and the complexity of the decoding logic is the same as in binary encoding, but the Hamming distance in Gray encoding is always 1.

Other encoding techniques include output-based encoding, MUSTANG,^[3] and NOVA^[4].

Motivation

The main idea in the design of state encoding for low power is to minimize the Hamming distance of the most probable state transitions, which reduces switching activity. Thus, a cost model for minimizing power consumption is to have a minimum-weighted Hamming distance (MWHD).^[1]^[2]

For counters, Gray encoding gives minimum switching activity, and thus is suitable for low-power designs. Gray encoding is best-suited to cases where state changes are sequential. In arbitrary state changes, FSM Gray code fail to be a low-power design. For such FSM, one-hot encoding guarantees switching of two bits for every state change. But since the number of state variables needed is equal to the number of states, as states increase, one-hot encoding becomes an impractical solution, mainly because with an increased number of inputs and outputs to the circuit, complexity and capacitive load increase. Binary coding is worst for low power since the maximum Hamming distance is equal to the number of state variables.

The need to have a solution for arbitrary-state-changing FSM has led to several state encoding techniques which focus on reducing the switching activity during state transitions.

Techniques

Column-based approach for low-power state assignment

This approach aims to reduce power dissipation by sequential circuits by choosing state assignments which minimize the switching activity between state transitions. Thus the combinational part of FSM has lower input transition probability and is more like to give low power dissipation when synthesized. This algorithm uses a boolean matrix with rows corresponding to state codes and columns corresponding to state variables. One state variable is considered at a time, and the algorithm tries to assign its value to each state in FSM, in a way which is likely to minimize the switching activity for the complete assignment. This procedure is repeated for the next variable. Since this minimization technique is applied column-by-column this technique is called the column-based approach.^[5]

Multi-code state assignment

The multi-code state assignment technique implements priority encoding by restraining redundant states. Thus, a state can be encoded using fewer state variables (bits). Further, flip-flops corresponding to those absent state variables can be clock-gated.^[6]

Profiling-based state assignment

This technique utilizes dynamic loop information extracted from FSM profiling data for state assignment in order to reduce switching activity. The procedure is as follows:^[7]

FSM state profiling collects information about the dynamic behavior of the FSM for a relevant input data set.
A loop detector searches for loops in the state trace, and each loop is stored and counted to obtain the frequency of the loops.
State assignment assigns state variables to each state based on the data gathered in the first two steps in order to minimize the switching activity. There are three algorithm to assign state variables:

Basic DFS state assignment algorithm
Loop-based DFS state assignment algorithm
Loop-based per-state heuristic state assignment algorithm

Other techniques

Some techniques encode state transition graphs (STG) to produce two-level and multi-level implementations targeting low power.^[8]^[9]
Re-encoding of existing logic-level sequential circuits for power optimizations has been proposed.^[10]
Spanning-tree-based state encoding^[11]
Depth-first methods^[12]
Minimum distance methods^[12]
1-level methods^[12]
1-level-tree method^[12], where focus is again on assigning state variables to the different states such that switching activity due to state transition is reduced
Apart from just encoding states for low power, some techniques involve decomposition of FSM into two or more sub-machines such that only one is active most of the time. The other sub-machine can be either clock-gated^[13] or power-gated.^[14]

Related Research Articles

In digital logic and computing, a counter is a device which stores the number of times a particular event or process has occurred, often in relationship to a clock. The most common type is a sequential digital logic circuit with an input line called the clock and multiple output lines. The values on the output lines represent a number in the binary or BCD number system. Each pulse applied to the clock input increments or decrements the number in the counter.

A finite-state machine (FSM) or finite-state automaton, finite automaton, or simply a state machine, is a mathematical model of computation. It is an abstract machine that can be in exactly one of a finite number of states at any given time. The FSM can change from one state to another in response to some inputs; the change from one state to another is called a transition. An FSM is defined by a list of its states, its initial state, and the inputs that trigger each transition. Finite-state machines are of two types—deterministic finite-state machines and non-deterministic finite-state machines. For any non-deterministic finite-state machine, an equivalent deterministic one can be constructed.

A logic gate is a device that performs a Boolean function, a logical operation performed on one or more binary inputs that produces a single binary output. Depending on the context, the term may refer to an ideal logic gate, one that has, for instance, zero rise time and unlimited fan-out, or it may refer to a non-ideal physical device.

<span class="mw-page-title-main">Digital electronics</span> Electronic circuits that utilize digital signals

Digital electronics is a field of electronics involving the study of digital signals and the engineering of devices that use or produce them. This is in contrast to analog electronics which work primarily with analog signals. Despite the name, digital electronics designs includes important analog design considerations.

In digital circuit design, register-transfer level (RTL) is a design abstraction which models a synchronous digital circuit in terms of the flow of digital signals (data) between hardware registers, and the logical operations performed on those signals.

In computer engineering, logic synthesis is a process by which an abstract specification of desired circuit behavior, typically at register transfer level (RTL), is turned into a design implementation in terms of logic gates, typically by a computer program called a synthesis tool. Common examples of this process include synthesis of designs specified in hardware description languages, including VHDL and Verilog. Some synthesis tools generate bitstreams for programmable logic devices such as PALs or FPGAs, while others target the creation of ASICs. Logic synthesis is one step in circuit design in the electronic design automation, the others are place and route and verification and validation.

In digital circuits and machine learning, a one-hot is a group of bits among which the legal combinations of values are only those with a single high (1) bit and all the others low (0). A similar implementation in which all bits are '1' except one '0' is sometimes called one-cold. In statistics, dummy variables represent a similar technique for representing categorical data.

In computer architecture, clock gating is a popular power management technique used in many synchronous circuits for reducing dynamic power dissipation, by removing the clock signal when the circuit, or a subpart of it, is not in use or ignores clock signal. Clock gating saves power by pruning the clock tree, at the cost of adding more logic to a circuit. Pruning the clock disables portions of the circuitry so that the flip-flops in them do not switch state, as switching the state consumes power. When not being switched, the switching power consumption goes to zero, and only leakage currents are incurred.

A ring counter is a type of counter composed of flip-flops connected into a shift register, with the output of the last flip-flop fed to the input of the first, making a "circular" or "ring" structure.

The algorithmic state machine (ASM) is a method for designing finite state machines (FSMs) originally developed by Thomas E. Osborne at the University of California, Berkeley (UCB) since 1960, introduced to and implemented at Hewlett-Packard in 1968, formalized and expanded since 1967 and written about by Christopher R. Clare since 1970. It is used to represent diagrams of digital integrated circuits. The ASM diagram is like a state diagram but more structured and, thus, easier to understand. An ASM chart is a method of describing the sequential operations of a digital system.

In digital logic, a don't-care term for a function is an input-sequence for which the function output does not matter. An input that is known never to occur is a can't-happen term. Both these types of conditions are treated the same way in logic design and may be referred to collectively as don't-care conditions for brevity. The designer of a logic circuit to implement the function need not care about such inputs, but can choose the circuit's output arbitrarily, usually such that the simplest, smallest, fastest or cheapest circuit results (minimization) or the power-consumption is minimized.

Logic optimization is a process of finding an equivalent representation of the specified logic circuit under one or more specified constraints. This process is a part of a logic synthesis applied in digital electronics and integrated circuit design.

An electronic circuit is composed of individual electronic components, such as resistors, transistors, capacitors, inductors and diodes, connected by conductive wires or traces through which electric current can flow. It is a type of electrical circuit. For a circuit to be referred to as electronic, rather than electrical, generally at least one active component must be present. The combination of components and wires allows various simple and complex operations to be performed: signals can be amplified, computations can be performed, and data can be moved from one place to another.

Low-power electronics are electronics, such as notebook processors, that have been designed to use less electrical power than usual, often at some expense. In the case of notebook processors, this expense is processing power; notebook processors usually consume less power than their desktop counterparts, at the expense of lower processing power.

<span class="mw-page-title-main">Digital signal</span> Signal used to represent data as a sequence of discrete values

A digital signal is a signal that represents data as a sequence of discrete values; at any given time it can only take on, at most, one of a finite number of values. This contrasts with an analog signal, which represents continuous values; at any given time it represents a real number within a continuous range of values.

In electronics, flip-flops and latches are circuits that have two stable states that can store state information – a bistable multivibrator. The circuit can be made to change state by signals applied to one or more control inputs and will output its state. It is the basic storage element in sequential logic. Flip-flops and latches are fundamental building blocks of digital electronics systems used in computers, communications, and many other types of systems.

Bus encoding refers to converting/encoding a piece of data to another form before launching on the bus. While bus encoding can be used to serve various purposes like reducing the number of pins, compressing the data to be transmitted, reducing cross-talk between bit lines, etc., it is one of the popular techniques used in system design to reduce dynamic power consumed by the system bus. Bus encoding aims to reduce the Hamming distance between 2 consecutive values on the bus. Since the activity is directly proportional to the Hamming distance, bus encoding proves to be effective in reducing the overall activity factor thereby reducing the dynamic power consumption in the system.

Glitch removal is the elimination of glitches—unnecessary signal transitions without functionality—from electronic circuits. Power dissipation of a gate occurs in two ways: static power dissipation and dynamic power dissipation. Glitch power comes under dynamic dissipation in the circuit and is directly proportional to switching activity. Glitch power dissipation is 20%–70% of total power dissipation and hence glitching should be eliminated for low power design.

Finite state machines (FSMs) are widely used to implement control logic in various applications such as microprocessors, digital transmission, digital filters and digital signal processing. Even for designs containing a good number of datapath elements, the controller occupies a sizeable portion. As the devices are mostly portable and hand-held, reducing power dissipation has emerged as the primary concern of today's VLSI designers. While the datapath elements can be shut down when they are not being used, controllers are always active. As a result, the controller consumes a good amount of system power. Thus, power-efficient synthesis of FSM has come up as a very important problem domain, attracting a lot of research. The synthesis method must be able to reduce both dynamic power and leakage power consumed by the circuit.

Low power flip-flops are flip-flops that are designed for low-power electronics, such as smartphones and notebooks. A flip-flop, or latch, is a circuit that has two stable states and can be used to store state information.

References

1 2 M. Pedram and A Abdollahi, “Low Power RT-Level Synthesis Techniques: A Tutorial”
1 2 Devadas & Malik, “A Survey of Optimization Techniques targeting Low Power VLSI Circuits”, DAC 32, 1995, pp. 242–247
↑ S. Devadas et al., “MUSTANG: State Assignment of Finite State Machines Targeting Multi-Level Logic Implementations,” IEEE Trans. Computer-Aided Design, Vol. CAD-7, No. 12, Dec. 1988, pp.129@1300
↑ T. Villa, A. S. Vincentell, “NOVA: State Assignment of Finite State Machines for Optimal Two-Level Logic Implementation,” IEEE transactions on CAD. VOL. 9 NO. 9. September 1990, pp. 905-924
↑ L. Benini and G. De Micheli, "State assignment for low power dissipation", IEEE J. Solid-State Circuits, vol. 30, no. 3, 1995, pp. 258–268
↑ X. Wu, M. Pedram, and L. Wang, Multi-code state assignment for low power design, IEEE Proceedings-Circuits, Devices and Systems, Vol. 147, No. 5, pp. 271–275, October 2000.
↑ http://mmc.tudelft.nl/sites/default/files/eggermont.pdf ^{[ bare URL PDF ]}
↑ K Roy and S Prasad. SYCLOP: Synthesis of CMOS Logic for Low Power Applications. In Proceedings of the Int’l Conference on Computer Design: VLSI in Computers and Processors, pages 464–467, October 1992
↑ C-Y Tsui, M Pedram, C-A Chen and A M Despain. Low Power State Assignment Targeting Two- and Multi-level Logic Implementations. In Proceedings of the Int’l Conference on Computer-Aided Design, pages 82–87, November 1994.
↑ G D Hachtel, M Hermida, A Pardo, M Poncino, and F Somenzi. Re-Encoding Sequential Circuits to Reduce Power Dissipation. In Proceedings of the Int’l Conference on Computer Aided Design, pages 70–73, November 1994
↑ W. Noth, and R. Kolla “Spanning Tree Based State Encoding for Low Power Dissipation,” Proceedings of DATE, pp. 168. Mar. 1999
1 2 3 4 "Archived copy" (PDF). home.deib.polimi.it. Archived from the original (PDF) on 28 August 2017. Retrieved 15 January 2022.{{cite web}}: CS1 maint: archived copy as title (link)
↑ J.C. Monteiro and A.L. Oliveira,"Implicit fsm decomposition applied to low-power design," IEEE Trans. VLSI Syst., vol.10, no.5, pp.560-565, 2002
↑ S.H. Chow, Y.C. Ho, T. Hwang and C.L. Liu, "Low power realization of finite state machines-a decomposition approach," ACM Trans. Design Automat. Elect. Syst., vol.1, no.3, pp.315-340, July 1996.

This page is based on this Wikipedia article
Text is available under the CC BY-SA 4.0 license; additional terms may apply.
Images, videos and audio are available under their respective licenses.

[ref2-1] 1 2 M. Pedram and A Abdollahi, “Low Power RT-Level Synthesis Techniques: A Tutorial”

[ref3-2] 1 2 Devadas & Malik, “A Survey of Optimization Techniques targeting Low Power VLSI Circuits”, DAC 32, 1995, pp. 242–247

[3] S. Devadas et al., “MUSTANG: State Assignment of Finite State Machines Targeting Multi-Level Logic Implementations,” IEEE Trans. Computer-Aided Design, Vol. CAD-7, No. 12, Dec. 1988, pp.129@1300

[4] T. Villa, A. S. Vincentell, “NOVA: State Assignment of Finite State Machines for Optimal Two-Level Logic Implementation,” IEEE transactions on CAD. VOL. 9 NO. 9. September 1990, pp. 905-924

[5] L. Benini and G. De Micheli, "State assignment for low power dissipation", IEEE J. Solid-State Circuits, vol. 30, no. 3, 1995, pp. 258–268

[6] X. Wu, M. Pedram, and L. Wang, Multi-code state assignment for low power design, IEEE Proceedings-Circuits, Devices and Systems, Vol. 147, No. 5, pp. 271–275, October 2000.

[7] ttp://mmc.tudelft.nl/sites/default/files/eggermont.pdf ^{[ bare URL PDF ]}

[8] K Roy and S Prasad. SYCLOP: Synthesis of CMOS Logic for Low Power Applications. In Proceedings of the Int’l Conference on Computer Design: VLSI in Computers and Processors, pages 464–467, October 1992

[9] C-Y Tsui, M Pedram, C-A Chen and A M Despain. Low Power State Assignment Targeting Two- and Multi-level Logic Implementations. In Proceedings of the Int’l Conference on Computer-Aided Design, pages 82–87, November 1994.

[10] G D Hachtel, M Hermida, A Pardo, M Poncino, and F Somenzi. Re-Encoding Sequential Circuits to Reduce Power Dissipation. In Proceedings of the Int’l Conference on Computer Aided Design, pages 70–73, November 1994

[11] W. Noth, and R. Kolla “Spanning Tree Based State Encoding for Low Power Dissipation,” Proceedings of DATE, pp. 168. Mar. 1999

[ref1-12] 1 2 3 4 "Archived copy" (PDF). home.deib.polimi.it. Archived from the original (PDF) on 28 August 2017. Retrieved 15 January 2022.{{cite web}}: CS1 maint: archived copy as title (link)

[13] J.C. Monteiro and A.L. Oliveira,"Implicit fsm decomposition applied to low-power design," IEEE Trans. VLSI Syst., vol.10, no.5, pp.560-565, 2002

[14] S.H. Chow, Y.C. Ho, T. Hwang and C.L. Liu, "Low power realization of finite state machines-a decomposition approach," ACM Trans. Design Automat. Elect. Syst., vol.1, no.3, pp.315-340, July 1996.

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

[11]

[12]

[13]

[14]