Institut für Systemdynamik - ISD
Refine
Year of publication
- 2019 (16) (remove)
Document Type
- Conference Proceeding (11)
- Article (3)
- Doctoral Thesis (1)
- Master's Thesis (1)
Language
- English (16)
Keywords
Institute
The Lempel-Ziv-Welch (LZW) algorithm is an important dictionary-based data compression approach that is used in many communication and storage systems. The parallel dictionary LZW (PDLZW) algorithm speeds up the LZW encoding by using multiple dictionaries. The PDLZW algorithm applies different dictionaries to store strings of different lengths, where each dictionary stores only strings of the same length. This simplifies the parallel search in the dictionaries for hardware implementations. The compression gain of the PDLZW depends on the partitioning of the address space, i.e. on the sizes of the parallel dictionaries. However, there is no universal partitioning that is optimal for all data sources. This work proposes an address space partitioning technique that optimizes the compression rate of the PDLZW using a Markov model for the data. Numerical results for address spaces with 512, 1024, and 2048 entries demonstrate that the proposed partitioning improves the performance of the PDLZW compared with the original proposal.
The Lempel–Ziv–Welch (LZW) algorithm is an important dictionary-based data compression approach that is used in many communication and storage systems. The parallel dictionary LZW (PDLZW) algorithm speeds up the LZW encoding by using multiple dictionaries. This simplifies the parallel search in the dictionaries. However, the compression gain of the PDLZW depends on the partitioning of the address space, i.e. on the sizes of the parallel dictionaries. This work proposes an address space partitioning technique that optimises the compression rate of the PDLZW. Numerical results for address spaces with 512, 1024, and 2048 entries demonstrate that the proposed address partitioning improves the performance of the PDLZW compared with the original proposal. These address space sizes are suitable for flash storage systems. Moreover, the PDLZW has relative high memory requirements which dominate the costs of a hardware implementation. This work proposes a recursive dictionary structure and a word partitioning technique that significantly reduce the memory size of the parallel dictionaries.
The Burrows–Wheeler transformation (BWT) is a reversible block sorting transform that is an integral part of many data compression algorithms. This work proposes a memory-efficient pipelined decoder for the BWT. In particular, the authors consider the limited context order BWT that has low memory requirements and enable fast encoding. However, the decoding of the limited context order BWT is typically much slower than the encoding. The proposed decoder pipeline provides a fast inverse BWT by splitting the decoding into several processing stages which are executed in parallel.
Flash memories are non-volatile memory devices. The rapid development of flash technologies leads to higher storage density, but also to higher error rates. This dissertation considers this reliability problem of flash memories and investigates suitable error correction codes, e.g. BCH-codes and concatenated codes. First, the flash cells, their functionality and error characteristics are explained. Next, the mathematics of the employed algebraic code are discussed. Subsequently, generalized concatenated codes (GCC) are presented. Compared to the commonly used BCH codes, concatenated codes promise higher code rates and lower implementation complexity. This complexity reduction is achieved by dividing a long code into smaller components, which require smaller Galois-Field sizes. The algebraic decoding algorithms enable analytical determination of the block error rate. Thus, it is possible to guarantee very low residual error rates for flash memories. Besides the complexity reduction, general concatenated codes can exploit soft information. This so-called soft decoding is not practicable for long BCH-codes. In this dissertation, two soft decoding methods for GCC are presented and analyzed. These methods are based on the Chase decoding and the stack algorithm. The last method explicitly uses the generalized concatenated code structure, where the component codes are nested subcodes. This property supports the complexity reduction. Moreover, the two-dimensional structure of GCC enables the correction of error patterns with statistical dependencies. One chapter of the thesis demonstrates how the concatenated codes can be used to correct two-dimensional cluster errors. Therefore, a two-dimensional interleaver is designed with the help of Gaussian integers. This design achieves the correction of cluster errors with the best possible radius. Large parts of this works are dedicated to the question, how the decoding algorithms can be implemented in hardware. These hardware architectures, their throughput and logic size are presented for long BCH-codes and generalized concatenated codes. The results show that generalized concatenated codes are suitable for error correction in flash memories, especially for three-dimensional NAND memory systems used in industrial applications, where low residual errors must be guaranteed.
This work introduces new signal constellations based on Eisenstein integers, i.e., the hexagonal lattice. These sets of Eisenstein integers have a cardinality which is an integer power of three. They are proposed as signal constellations for representation in the equivalent complex baseband model, especially for applications like physical-layer network coding or MIMO transmission where the constellation is required to be a subset of a lattice. It is shown that these constellations form additive groups where the addition over the complex plane corresponds to the addition with carry over ternary Galois fields. A ternary set partitioning is derived that enables multilevel coding based on ternary error-correcting codes. In the subsets, this partitioning achieves a gain of 4.77 dB, which results from an increased minimum squared Euclidean distance of the signal points. Furthermore, the constellation-constrained capacities over the AWGN channel and the related level capacities in case of ternary multilevel coding are investigated. Simulation results for multilevel coding based on ternary LDPC codes are presented which show that a performance close to the constellation-constrained capacities can be achieved.
It is well known that signal constellations which are based on a hexagonal grid, so-called Eisenstein constellations, exhibit a performance gain over conventional QAM ones. This benefit is realized by a packing and shaping gain of the Eisenstein (hexagonal) integers in comparison to the Gaussian (complex) integers. Such constellations are especially relevant in transmission schemes that utilize lattice structures, e.g., in MIMO communications. However, for coded modulation, the straightforward approach is to combine Eisenstein constellations with ternary channel codes. In this paper, a multilevel-coding approach is proposed where encoding and multistage decoding can directly be performed with state-of-the-art binary channel codes. An associated mapping and a binary set partitioning are derived. The performance of the proposed approach is contrasted to classical multilevel coding over QAM constellations. To this end, both the single-user AWGN scenario and the (multiuser) MIMO broadcast scenario using lattice-reduction-aided preequalization are considered. Results obtained from numerical simulations with LDPC codes complement the theoretical aspects.