The Two-Modular Fourier Transform of Binary Functions

DOI10.1109/TIT.2016.2545678MaRDI QIDQ2976868zbMATH OpenWikidataFDO

Authors Yi Hong, Emanuele Viterbo, Jean-Claude Belfiore

Publication date 28 April 2017

Published in IEEE Transactions on Information Theory (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1603.06173

Mathematics Subject Classification ID

Fourier and Fourier-Stieltjes transforms on locally compact and other abelian groups (43A25) Application of orthogonal and other special functions (94A11)

Abstract: In this paper, we provide a solution to the open problem of computing the Fourier transform of a binary function defined over $n$-bit vectors taking $m$-bit vector values. In particular, we introduce the two-modular Fourier transform (TMFT) of a binary function $f:GightarrowcalR$, where $G=(mathbb{F}_2^n,+)$ is the group of $n$ bit vectors with bitwise modulo two addition $+$, and $calR$ is a finite commutative ring of characteristic $2$. Using the specific group structure of $G$ and a sequence of nested subgroups of $G$, we define the fast TMFT and its inverse. Since the image $calR$ of the binary functions is a ring, we can define the convolution between two functions $f:GightarrowcalR$. We then provide the TMFT properties, including the convolution theorem, which can be used to efficiently compute convolutions. Finally, we derive the complexity of the fast TMFT and the inverse fast TMFT.

This page was built for publication: The Two-Modular Fourier Transform of Binary Functions

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2976868)