Sequences and Linear Codes from Highly Nonlinear Functions
Chunlei Li · NORA - Norwegian Open Research Archives · 2014
Due to optimal nonlinearity and differential uniformity, perfect nonlinear (PN) and almost perfect nonlinear (APN) functions are of great importance in cryptography. It is interesting that they also define optimal objects in other domains of mathematics and information theory. This dissertation is devoted to exploring the application of highly nonlinear functions, especially PN and APN functions, to the construction of low-correlation sequences and optimal linear codes. For an arbitrary odd prime p, there are only two basic classes of two-level auto-correlation p-ary sequences with no subfield structures: the msequences and the Helleseth-Gong sequences, where Helleseth-Gong sequences are closely related to a class of p-ary perfect nonlinear functions. Papers I and II are dedicated to investigating the cross-correlation between the p-ary m-sequences and d-decimated Helleseth-Gong sequences for some decimations d, and to constructing sequence families with low correlation from them. Papers III-IV have focused on the study of linear codes defined from highly nonlinear functions. Paper III utilizes some highly nonlinear functions including PN and APN functions to construct ternary cyclic codes with the optimal minimum (Hamming) distance. Paper IV further investigates the weight distribution of some optimal cyclic codes proposed in Paper III. Paper V examines the covering radius of some linear codes defined from PN and APN functions and presents a number of quasi-perfect linear codes.