Search

Recent years have seen dramatic growth in Internet usage and an increasing convergence between Internet and wireless communications. There has also been renewed interest in iteratively decoded low-density parity-check (LDPC) codes due to their capacity approaching performance on AWGN channels.

In this dissertation, we investigate the problem of designing an ultra-low power $M$-ary frequency shift keying (MFSK) system. In Chapter 2, We design a communication system that operates under stringent power constraints, but is flexible with bandwidth constraints. Our approach is to consider some of the key elements in a transceiver and optimize them for low power consumption, as opposed to optimizing them to minimize, say, average probability of error. An obvious consequence of this is that high complexity components of the system, such as matched filters, forward error correction that employs iterative decoders, coherent demodulators, and bandwidth-efficient modulation formats, are not feasible for this research. Rather, our system is designed using MFSK with non-coherent detection, optimized two-pole bandpass filters (BPF), and Reed-Solomon (RS) codes with hard-decision decoding. Among other things, we show that by properly optimizing the key parameters of the BPFs and RS codes, we can design the system to be significantly less complex than an optimal one, and only lose about 1.2 dB in terms of performance.In Chapter 3, We extend the results from Chapter 2 to incorporate fast frequency hopping (FFH) and intelligent jamming. The system still operates under stringent power constraints, but is flexible with bandwidth constraints. Our system is designed using MFSK with non-coherent detection and fast frequency hopping (FFH), optimized two-pole BPF, and RS codes with hard-decision decoding. Among other things, we show that by properly optimizing the key parameters of the BPFs and RS codes, we can design the system to be significantly less complex than the MF system with a performance loss of less than 1.4 dB in terms of performance in most scenarios that we considered. Further, the 2-pole BPF system can actually outperform the corresponding MF system by up to 2.4 dB with multi-tone jamming.In Chapter 4, we extend the results from Chapter 2 to incorporate Gaussian filtering. We improve our previous design by considering the power-bandwidth tradeoff, and we show that we can save a large percentage of system bandwidth by sacrificing a small amount of power, when the demodulator and coding parameters are optimized. For example, we can save 50\% of system bandwidth at the cost of 1 dB loss in performance compared to our previous system design. We quantify the performance loss as a function of both the system bandwidth saved and the time-bandwidth product of the Gaussian filter. We keep $M = 16$ as our baseline design, and compare the performance of the $M$-ary GFSK system with the corresponding MFSK system.

The performance of a packet-level iterative detection technique is examined for a slow-frequency-hop packet radio system using interleaved Reed-Solomon codes and per-dwell differential encoding. A per-dwell soft-input-soft-output detector along with successive-erasures decoding results in a system that performs better than previously considered detection techniques in the presence of partial-band interference. The log-MAP algorithm and two forms of its max-log-MAP approximation are considered for the soft-input-soft-output detector along with different channel estimators. The performance and detection complexity of the systems is compared. A limit on the number of erasures allowed in successive-erasures decoding is also considered, and its effect on the system's performance and detection complexity is examined.

Algebraic soft-decision decoding (ASD) algorithms of Reed-Solomon (RS) codes have attracted much interest due to their significant coding gain and polynomial complexity. Practical ASD algorithms include the Koetter-Vardy, low-complexity Chase (LCC) and bit-level generalized minimum distance (BGMD) decodings. This thesis focuses on the design of efficient VLSI architectures for ASD decoders.One major step of ASD algorithms is the interpolation. Available interpolation algorithms can only add interpolation points or increase interpolation multiplicities. However, backward interpolation, which eliminates interpolation points or reduces multiplicities, is indispensable to enable the re-using of interpolation results. In this thesis, a novel backward interpolation is first proposed for the LCC decoding through constructing equivalent Gröbner bases. In the LCC decoding, 2η test vectors need to be interpolated over. With backward interpolation, the interpolation result for each of the second and later test vectors can be computed by only one backward and one forward interpolation iterations. Compared to the previous design, the proposed backward-forward interpolation scheme can lead to significant memory saving. To reduce the interpolation latency of the LCC decoding, a unified backward-forward interpolation is proposed to carry out both interpolations in a single iteration. With only 40% area overhead, the proposed unified interpolation architecture can almost double the throughput when large η is adopted. Moreover, a reduced-complexity multi-interpolator scheme is developed for the low-latency LCC decoding. The proposed backward interpolation is further extended to the iterative BGMD decoding. By reusing the interpolation results, at least 40% of the interpolation iterations can be saved for a (255, 239) code while the area overhead is small. Further speedup of the BGMD interpolation is limited by the inherent serial nature of the interpolation algorithm. In this thesis, a novel interpolation scheme that can combine multiple interpolation iterations is developed. Efficient architectures are presented to integrate the combined and backward interpolation techniques. A combined-backward interpolator of a (255, 239) code is implemented and can achieve a throughput of 440 Mbps on a Xilinx XC2V4000 FPGA device. Compared to the previous fastest implementation, our implementation can achieve a speedup of 64% with 51% less FPGA resource.The factorization is another major step of ASD algorithms. In the re-encoded LCC decoding, it is proved that the factorization step can be eliminated. Hence, the LCC decoder can be further simplified. In the re-encoded ASD decoders, a re-encoder and an erasure decoder need to be added. These two blocks can take a significant proportion of the overall decoder area and may limit the achievable throughput. An efficient re-encoder design is proposed by computing the erasure locator and evaluator through direct multiplications and reformulating other involved computations. When applied to a (255, 239) code, our re-encoder can achieve 82% higher throughput than the previous design with 11% less area. With minor modifications, the proposed design can also be used to implement erasure decoder.After applying available complexity-reducing techniques, complexity comparisons for three practical ASD decoders were carried out. It is derived that the LCC decoder can achieve similar or higher coding gain with lower complexity for high-rate codes. This thesis also provides discussions on how the hardware complexities of ASD decoders change with codeword length, code rate and other parameters.

Read channel architectures based on a single low-density parity-check (LDPC) code are being considered for the next generation of hard disk drives. However, LDPC-only solutions suffer from the error floor problem, which may compromise reliability, if not handled properly. Concatenated architectures using an LDPC code plus a Reed-Solomon (RS) code lower the error-floor at high signal-to-noise ratio (SNR) at the price of a reduced coding gain and a less sharp waterfall region at lower SNR. This architecture fails to deal with the error floor problem when the number of errors caused by multiple dominant trapping sets is beyond the error correction capability of the outer RS code. The ultimate goal of a sharper waterfall at the low SNR region and a lower error floor at high SNR can be approached by introducing a parallel subspace subcode RS (SSRS) code (PSSRS) to replace the conventional RS code. In this new LDPC+PSSRS system, the PSSRS code can help localize and partially destroy the most dominant trapping sets. With the proposed iterative parallel local decoding algorithm, the LDPC decoder can correct the remaining errors by itself. The contributions of this work are: 1) We propose a PSSRS code with parallel local SSRS structure and a three-level decoding architecture, which enables a trade off between performance and complexity; 2) We propose a new LDPC+PSSRS system with a new iterative parallel local decoding algorithm with a 0.5dB+ gain over the conventional two-level system. Its performance for 4K-byte sectors is close to the multiple LDPC-only architectures for perpendicular magnetic

This manuscript describes a number of algorithms that can be used to quickly evaluate a polynomial over a collection of points and interpolate these evaluations back into a polynomial. Engineers define the 'Fast Fourier Transform' as a method of solving the interpolation problem where the coefficient ring used to construct the polynomials has a special multiplicative structure. Mathematicians define the 'Fast Fourier Transform' as a method of solving the evaluation problem. One purpose of the document is to provide a mathematical treatment of the topic of the 'Fast Fourier Transform' that can also be understood by someone who has an understanding of the topic from the engineering perspective. The manuscript will also introduce several new algorithms that solve the fast multipoint evaluation problem over certain finite fields and require fewer finite field operations than existing techniques. The document will also demonstrate that these new algorithms can be used to multiply polynomials with finite field coefficients with fewer operations than Schonhage's algorithm in most circumstances. A third objective of this document is to provide a mathematical perspective of several algorithms which can be used to multiply polynomials of size which is not a power of two. Several improvements to these algorithms will also be discussed. Finally, the document will describe several applications of the 'Fast Fourier Transform' algorithms presented and will introduce improvements in several of these applications. In addition to polynomial multiplication, the applications of polynomial division with remainder, the greatest common divisor, decoding of Reed-Solomon error-correcting codes, and the computation of the coefficients of a discrete Fourier Series will be addressed.

In this thesis, an FPGA implementation of a factorization processor for algebraic soft-decision Reed-Solomon (RS) decoding is first presented. The design is based on the root-order prediction architecture and extensible for the factorization of polynomials with designated degrees. Parallel processing is exploited to speed up the polynomial updating involved in the factorization. To resolve the data dependency issue in parallel polynomial updating, an efficient coefficient storage and transfer scheme with small memory requirement and low latency is proposed. Synthesis results show that the factorization processor for a (255, 239) RS code with maximum multiplicity four can achieve an average decoding speed of 226 Mbps on a Xilinx Virtex-II FPGA device when the frame error rate is less than 10-2.Next, an FPGA implementation of a factorization processor for algebraic soft-decision bit-level generalized minimum distance (BGMD) RS decoding is presented. The BGMD factorization processor utilizes a low-latency and prediction-free scheme for root computation. Furthermore, parallel processing architectures and efficient coefficient storage schemes are employed to reduce the latency. Synthesis results show that the BGMD factorization processor for a (255, 239) RS code with maximum multiplicity two can achieve a decoding speed of 815 Mbps on a Xilinx Virtex-II FPGA device.Prior research efforts have been focusing on using BCH codes for error correction in multi-level cell (MLC) NAND flash memory. However, BCH codes often require highly parallel implementations to meet the throughput requirement. As a result, large area is needed. In this thesis, RS codes are proposed to be used for the error correction inMLC flash memory. A (828, 820) RS code has almost the same rate and length in terms of bits as a BCH (8248, 8192) code. Moreover, it has at least the same error-correcting performance in flash memory applications. Nevertheless, with 70% of the area, the RS decoder can achieve a throughput that is 121% higher than the BCH decoder. A novel bit mapping scheme using Gray code is also proposed. Compared to direct bit mapping, the proposed scheme can achieve 0.02 dB and 0.2dB additional gains by using RS and BCH codes, respectively, without any overhead.

Please download dissertation to view abstract.

This research is concerned with the reliable delivery of scalable compressed data over lossy communication channels. Recent works proposed several strategies for assigning optimal code redundancies to elements of scalable data, which form a linear structure of dependency, under the assumption that all source elements are encoded onto a common group of network packets. Given large data and small network packets, such schemes require very long channel codes with high computational complexity. In networks with high loss, small packets are more desirable than long packets. The first contribution of this thesis is to propose a strategy for optimally assigning elements of the scalable data to clusters of packets, subject to constraints on packet size and code complexity. Given a packet cluster arrangement, the scheme then assigns optimal code redundancies to the source elements, subject to a constraint on transmission length. Experimental results show that the proposed strategy can outperform the previous code assignment schemes subject to the above-mentioned constraints, particularly at high channel loss rates. Secondly, we modify these schemes to accommodate complex structures of dependency. Source elements are allocated to clusters of packets according to their dependency structure, subject to constraints on packet size and channel codeword length. Given a packet cluster arrangement, the proposed schemes assign optimal code redundancies to the source elements, subject to a constraint on transmission length. Experimental results demonstrate the superiority of the proposed strategies for correctly modelling the dependency structure. The last contribution of this thesis is to propose a scheme for optimizing protection of scalable data where limited retransmission is possible. Previous work assumed that retransmission is not possible. For most real-time or interactive applications, however, retransmission of lost data may be possible up to some limit. In the present work we restrict our attention to streaming sources (e.g., video) where each source element can be transmitted in one or both of two time slots. An optimization algorithm determines the transmission and level of protection for each source element, using information about the success of earlier transmissions. Experimental results confirm the benefit of limited retransmission.

Cellular Digital Packet Data (CDPD) is a new wireless packet data communications system which was developed by a consortium of U.S. cellular service providers to augment their voice communications systems. The main goal of the CDPD system design was to provide wireless packet data connectivity to mobile data communications customers. This thesis presents fundamental information required to successfully implement CDPD base station or mobile equipment. This information includes an introduction to the operation of data networks, a discussion of Gaussian Filtered Minimum Shift Keying (GMSK), and a detailed analysis of Reed-Solomon error correction codes.