Efficient methods for finding optimal convolutional self-doubly orthogonal codes.

摘要

In recent years, the rise of ultrabooks and mobile devices has been accompanied by an ever in- creasing need for reliable high-bandwidth wireless communications. To mitigate or eliminate the errors that are invariably introduced due to noise and interference in the communication channels, it is important to develop efficient error-correcting coding schemes. Indeed, these codes may be used to preserve the error performance while allowing the data-rate of digital communications to be increased and the transmission power at lower signal-to-noise ratios to be reduced, thereby improving the overall power efficiency of these devices.;In this manuscript-based thesis, we present an efficient search algorithm for finding optimal/short-span Convolutional Self-Doubly Orthogonal (CDO) codes and Simplified Convolutional Self-Doubly Orthogonal (S-CDO) codes. These error-correcting codes are employed in an iterative error-control coding scheme that differs from the classical Turbo code procedure, as it does not require any interleaver, neither at the encoding nor at the decoding stages. However, its iterative threshold decoding procedure requires that these systematic convolutional codes satisfy some "double orthogonality properties", beyond those of the well- known orthogonal codes used in the usual non-iterative threshold decoding. In order to build high-performance, low-latency codecs with these codes, it is important to minimize the constraint length, also called "span", for a given number J of generator connections. Although finding CDO/S-CDO codes is not difficult, determining the optimal/short-span codes for a given order J is computationally very challenging. The direct construction of optimal or shortest-span CDO and S-CDO codes has so far eluded analysis, and the search for these codes is believed to be an NP-complete problem.;The thesis presents a total of three articles: two articles that were published in IEEE Transactions on Communications, and one article that was submitted for publication to IEEE Transactions on Parallel and Distributed Systems. In these articles, we describe a novel efficient and parallel implicitly-exhaustive search algorithm for finding rate R = 1/2 systematic optimal/short-span CDO and S-CDO codes. The high-performance search algorithm is still exhaustive in nature, yet it provides an impressive speedup that is larger than 16300 (CDO, J=7) and 6300 (S-CDO, J=8) over the reference implicitly-exhaustive search algorithm, and larger than 2000 (CDO, J=17) over the fastest known CDO validation function used in high-performance pseudo-random search algorithms.;These speedups are achieved through algorithmic enhancements in the deterministic search-space reduction, and a vastly improved validation function that makes use of a novel data structure for enabling data-reuse and incremental computations. The resulting validation function speedup is larger than 60000 (S-CDO, J=17) and 190000 (CDO, J=17) when compared to its reference implementation. The combination of optimizations and load- balancing techniques allowed us to leverage hundreds of processor cores in order to perform an exhaustive search over a search space that is some 1014 times larger than what was previously possible, yielding new and improved codes in a reasonable computation time.;We provide optimal-span CDO/S-CDO codes having orders J ∈ {6,...,9} and J ∈ {9,...12} respectively, as well as CDO/S-CDO codes having the shortest spans published to date for J ∈ {10,...,17} and for J ∈ {13,...,20} respectively. Using this algorithm, we were able to reduce the spans of these codes by an average of 14% for CDO codes and by an average of 26% for S-CDO codes, resulting in a latency reduction of the same magnitude in the error-correcting systems for which they are intended.;We compare the spans of our new codes to known theoretical lower-bounds, and provide the error-correction performance for some of these codes, along with the span improvements obtained when using S-CDO codes instead of CDO codes of the same order. We show that although CDO codes perform slightly better than S-CDO codes, from an engineering point of view, S-CDO codes clearly offer a much lower decoding latency for a similar error performance. We also confirm that for moderate Eb/N0 values (i.e. Eb/N0 > 3dB), CDO/S-CDO codes do offer a competitive error performance and a compelling alternative to Turbo codes, since their error performance curves yield a lower "floor" region than that of Turbo codes, thus providing a better error performance along with a lower latency and reduced implementation complexity.;Finally, we present the evolution of the error performance of CDO/S-CDO codes as a function of their order J. We show that although the greater the value of J, the better the error performance, this is achieved at the cost of having the waterfall" region of the error performance move to higher values of Eb/N0.