FLAP Journal 2023 Journal Article
On Representation of Maximally Asymmetric Functions Based on Decision Diagrams.
- Shinobu Nagayama
- Tsutomu Sasao
- Jon T. Butler
Maximally asymmetric functions are multiple-valued functions that have the maximum distance from their nearest symmetric functions, in terms of Hamming distance. Maximally asymmetric functions can be promising for ap- plications such as radio communication and cryptography, due to randomness of the functions. To promote such application studies, benchmarks for maxi- mally asymmetric functions in compact form are needed. However, few studies on benchmark generation or even on characteristics for maximally asymmet- ric functions have been reported. Thus, this paper investigates representation of maximally asymmetric functions based on decision diagrams. This paper begins with proposing a method to compute asymmetry of a given function easily, and then, derives a new characteristic of maximally asymmetric func- tions based on the computation method. Using the derived characteristic, we also propose a method to automatically generate benchmarks for maximally asymmetric functions represented by decision diagrams. By comparing sizes of different types of decision diagrams, we consider suitable representations for maximally asymmetric functions. This paper is an extension of [24].