A Halting Algorithm to Determine the Existence of the Decoder

作者：Shen, ShengYu^*; Qin, Ying; Xiao, LiQuan; Wang, KeFei; Zhang, JianMin; Li, SiKun

来源：IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, 2011, 30(10): 1556-1563.

DOI：10.1109/TCAD.2011.2159792

• Complementary synthesis
• halting algorithm

Complementary synthesis automatically synthesizes the decoder circuit of an encoder. It determines the existence of the decoder by checking whether the encoder's input can be uniquely determined by its output. However, this algorithm will not halt if the decoder does not exist. To solve this problem, a novel halting algorithm is proposed. For every path of the encoder, this algorithm first checks whether the encoder's input can be uniquely determined by its output. If yes, the decoder exists; otherwise, this algorithm checks if this path contains loops, which can be further unfolded to prove the non-existence of the decoder for all those longer paths. To illustrate its usefulness and efficiency, this algorithm has been run on several complex encoders, including PCI-E and Ethernet. Experimental results indicate that this algorithm always halts properly by distinguishing correct encoders from incorrect ones, and it is more than three times faster than previous ones.

• 出版日期2011-10
• 单位中国人民解放军国防科学技术大学