Polar codes, introduced by Arikan in 2009, have attracted considerable interest as an asymptotically capacity-achieving code with sufficient performance advantages to merit inclusion in the 5G standard. Polar codes are constructed directly from an explicit model of the communication channel, so their performance is dependent on a detailed understanding of the transmission environment. We partially remove a basic assumption in coding theory that channels are identical and independent by extending polar codes to several types of channels with memory, including periodic Markov processes and Information Regular processes. In addition, we consider modifications to the polar code construction so that the inclusion of a shared secret in the frozen set naturally produces encryption via one-time pad. We describe one such modification in terms of the achievable frozen sets which are compatible with the polar code automorphism group. We then provide a partial characterization of these frozen sets using an explicit construction for the Linear Extension Diameter of channel entropies. / Doctor of Philosophy / Efficient, reliable communication has become an essential component of modern society. Error-correcting codes allow for the use of redundant symbols to fix errors in transmission. While it has long been known that communication channels have an inherent capacity describing the optimal redundancy required for reliable transmission, explicit constructions which achieve this capacity have proved elusive. Our focus is the recently discovered family of polar codes, which are known to be asymptotically capacity-achieving. Polar codes also perform well enough in practice to merit inclusion in the 5G wireless standard shortly after their creation. The polarization process uses an explicit model of the channel and a recursive construction to concentrate errors in a few symbols (called the frozen set), which are then simply ignored. This reliance on an explicit channel model is problematic due to a long-standing assumption in coding theory that the probability of error in each symbol is identical and independent. We extend existing results to explore persistent sources of interference modelling environments such as nearby power lines or prolonged outages. While polar codes behave quite well in these new settings, some forms of memory can only be overcome using very long codewords. We next explore an application relating to secure communication, where messages must be recovered by a legitimate receiver but not by an eavesdropper. Polar codes behave quite well in this environment as well, as we can separately compute which symbols can be recovered by each party and use only those with the desired properties. We extend a recent result which proposes the use of a shared secret in the code construction to further complicate recovery by an eavesdropper. We consider several modifications to the construction of polar codes which allow the shared secret to be used for encryption in addition to the existing information theoretic use. We discover that this task is closely related to the unsolved problem of determining which symbols are in the frozen set for a particular channel. We conclude with partial results to this problem, including two choices of frozen set which are, in some sense, maximally separated.
| Identifer | oai:union.ndltd.org:VTETD/oai:vtechworks.lib.vt.edu:10919/115053 |
| Date | 15 May 2023 |
| Creators | Timmel, Stephen Nicholas |
| Contributors | Mathematics, Matthews, Gretchen L., Klaus, Martin, Michaels, Alan J., Shimozono, Mark M. |
| Publisher | Virginia Tech |
| Source Sets | Virginia Tech Theses and Dissertation |
| Language | English |
| Detected Language | English |
| Type | Dissertation |
| Format | ETD, application/pdf, application/x-zip-compressed |
| Rights | In Copyright, http://rightsstatements.org/vocab/InC/1.0/ |
Page generated in 0.0019 seconds