FSM

Background

In logic synthesis of Finite State Machines (FSMs) the problem of state-assignment is well-known. Generally, in state-assignment, the approach is to minimize the number of flip-flops to encode the state. Several methods exists however in logic synthesis tools to perform state-encoding, such as one-hot and Gray coding.

With the observation that Moore’s Law is ending it is expected that logic circuits become unreliable. Today this is already the case in various types of memories, where both error correction and block redundancy techniques are applied. In various professional fields, such as aerospace, reliability is already a major concern but hardware cost is often a less important issue. Many (classic) fault tolerant techniques are being applied, such as triple modular redundancy (TMR). In the coming years reliability is also becoming an issue in low-cost consumer ICs, and here the challenge is to improve reliability within strict cost constraints.

Assignment

In short: the challenge in this assignment is to find new state encoding techniques which allow for bit-flips to happen in the state register without influencing the external behaviour of the Finite State Machine.

As a starting point existing state-encoding techniques should be revisited and qualified on their resiliency against bit failures.

Approach

After a literature study on fault tolerance and error resilient techniques and with basic knowledge of information coding theory it is the intention to qualify the cost and error-resilience capability of various encoding techniques. The research question to be answered is: Are there encoding techniques for generic FSMs which provide fault tolerance competitive in cost as compared to TMR.

As research tool the intention is to use the ABC logic synthesis tool of UCBerkeley for experimentation.

Requirements

  • you feel challenged by reliability in future VLSI technologies in the light of Moore’s law ending.
  • you have basic knowledge in coding theory
  • you are proficient in C and python
  • you prefer working in GNU/Linux or another POSIX-compatible OS

Timing

starting date is flexible, preferably a.s.a.p.

Contact