Binary Frames, Codes and Euclidean Embeddings

This dissertation has two parts. The first part is concerned with using Euclidean embeddings and random hyperplane tessellations to construct binary block codes. The construction proceeds in two stages. First, an auxiliary ternary code is chosen which consists of vectors in the union of coordinate subspaces. The subspaces are selected so that any two vectors of different support have a sufficiently large distance. In addition, any two ternary vectors from the auxiliary codebook with common support are at a guaranteed minimum distance. In the second stage, the auxiliary ternary code is converted to a binary code by an additional random hyperplane tessellation. The second part of this dissertation is dedicated to Binary Parseval frames, which share many structural properties with real and complex ones. On the other hand, there are subtle differences, for example that the Gramian of a binary Parseval frame is characterized as a symmetric idempotent whose range contains at least one odd vector. Here, we study binary Parseval frames obtained from the orbit of a vector under a group representation, in short, binary Parseval group frames. In this case, the Gramian of the frame is in the algebra generated by the right regular representation. We identify equivalence classes of such Parseval frames with binary functions on the group that satisfy a convolution identity. This allows us to find structural constraints for such frames. We use these constraints to catalogue equivalence classes of binary Parseval frames obtained from group representations. As an application, we study the performance of binary Parseval frames generated with abelian groups for purposes of error correction. We show that if p is an odd prime, then the group Zq/p is always preferable to Zq/p when searching for best performing codes associated with binary Parseval group frames.