A Mathematical Theory of Communication with Graphs and Symbols
This work will introduce a channel conceptualization and possible coding scheme for Graph-and-Symbol (GS) Communication. While Claude Shannon’s mathematical model for communication employed graphs to describe relationships and confusability among traditional time-sequenced signals, little work as been done to describe non-linear communication with graphs where we transmit and receive physical structures of information. The principal contribution of this work is to introduce a mathematical framework for communication with graphs which have symbols assigned to vertices. This looks like a molecule, and so we may think of these messages as coded forms of molecular communication.
At this time, many problems in this area will (and may remain) computationally intractable, but as the field of graph theory continues to develop, new tools and techniques may emerge to solve standing problems in this new subfield of communication.
Graphs present two difficulties: first, they contain ambiguities among their vertices and do not have an a priori canonical ordering, and second, the relationships among graphs lack structural regularities which we see in traditional error control coding lattices. There are no Galois fields to exploit over graph-based codes as we have with cyclic codes, for example. Furthermore, the shear number of graphs of order n grows so rapidly that it is difficult to account for the neighborhoods around codewords and effectively reduce communication errors which may occur. The more asymmetric a graph is, the more orderings on symbols it can support. However, asymmetries complicate the computation of channel transition probabilities, which are the cornerstone of all communication theory.
In the prologue, the reader will be introduced to a new educational tool for designing traditional binary cyclic codes.
1 through 10 will detail the development of Graph-and-Symbol (GS) Commu- nication to date followed by two example codes which demonstrate the power of structuring information on graphs.
Chapter 13 onward will review the preliminary work in another area of research, disjoint from the main body. It is included here for posterity and special interests in applying graphs to solving other problems in signal processing. It begins with an introduction of spacetime raythic graphs. We propose a new chamfering paradigm for connecting neighboring pixels which approximates solutions to the eikonal equation. We show that some raythic graphs possess structures with multiple, differing solutions to eikonal wavefront propagation which are essential to the construction of the Umbral Transform. This umbral transform emulates ray casting effects, such as shadows and diffraction within an image space, from a network-flow algorithm.
This work may be duplicated in whole or in part for educational purposes only. All other rights of this work are reserved by the author, Timothy Arthur Terlep Jr., of Rose-Hulman Institute of Technology, Terre Haute, IN (effective August 2024), and subject to the rules and regulations of the Graduate School of Purdue University.
Readers may contact the author with any comments and questions at taterlep@gmail.com
History
Degree Type
- Doctor of Philosophy
Department
- Electrical and Computer Engineering
Campus location
- West Lafayette
Advisor/Supervisor/Committee Chair
Mark R. BellAdvisor/Supervisor/Committee co-chair
Thomas M. TalavageAdditional Committee Member 2
David J. LoveAdditional Committee Member 3
Joseph RispoliUsage metrics
Categories
- Data communications
- Molecular, biological, and multi-scale communications
- Signal processing
- Communications engineering not elsewhere classified
- Engineering education
- Spatial data and applications
- Coding, information theory and compression
- Combinatorics and discrete mathematics (excl. physical combinatorics)