Computing the Kernel of a Non-Linear Code

Abstract

Given a binary code $C$, the set $K$ of all vectors which leave $C$ invariant under translation is called the kernel of $C$. The main concern of this paper is the development of an efficient algorithm for computing the kernel of $C$. We present such an algorithm with runtime $O(|C|\log |C|)$, which is the best possible.