Geometric source coding and vector quantization

A geometric formulation is presented for source coding and vector quantizer design. Motivated by the asymptotic equipartition principle, the authors consider two broad classes of source codes and vector quantizers: elliptical codes and quantizers based on the Gaussian density function, and pyramid codes and quantizers based on the Laplacian density function. Elliptical and weighted pyramid vector quantizers are developed by selecting codewords as points in a lattice that lie on (or near) a specified ellipse or pyramid. The combination of geometric structure and lattice basis allows simple encoding and decoding algorithms     

Hybrid Hard-Decision Iterative Decoding of Irregular Low-Density Parity-Check Codes

Time-invariant hybrid (Hscr_TI) decoding of irregular low-density parity-check (LDPC) codes is studied. Focusing on Hscr_TI algorithms with majority-based (MB) binary message-passing constituents, we use density evolution (DE) and finite-length simulation to analyze the performance and the convergence properties of these algorithms over (memoryless) binary symmetric channels. To apply DE, we generalize degree distributions to have the irregularity of both the code and the decoding algorithm embedded in them. A tight upper bound on the threshold of MB Hscr_TI algorithms is derived, and it is proven that the asymptotic error probability for these algorithms tends to zero, at least exponentially, with the number of iterations. We devise optimal MB Hscr_TI algorithms for irregular LDPC codes, and show that these algorithms outperform Gallager's algorithm A applied to optimized irregular LDPC codes. We also show that compared to switch-type algorithms, such as Gallager's algorithm B, where a comparable improvement is obtained by switching between different MB algorithms, MB Hscr_TI algorithms are more robust and can better cope with unknown channel conditions, and thus can be practically more attractive     

Hexacode-based quantization of the Gaussian source at 1/2 bit persample

We present the performance of several suboptimal algebraic quantizers in 24 dimensions. The Gaussian source is encoded at 1/2 bit per sample using the binary extended Golay code C₂₄ and the hexacode H₆. We also propose two new suboptimal decoding algorithms for the hexacode H₆     

Fourier Transform Vector Quantization for Speech Coding

Design algorithms and simulation results are presented for vector quantizers for Fourier transformed data. Transforming the data prior to quantization has two potential advantages. First, each sample in the transform domain depends on many samples in the original domain. Thus, even scalar quantization in the transform domain is a form of vector quantization or block source coding in the original waveform domain and the basic coding theorems of information theory show that such block codes can provide better performance than scalar codes, even for memoryless sources. Second, vector quantization of Fourier transformed speech waveforms provides distinctly better subjective quality than ordinary vector quantization of the waveform using codes of comparable complexity. While the system is, of course, more complicated due to the need to take Fourier transforms, its envisioned application is as a coder for the output of FFT chips currently available or under development. The proposed implementation of a Fourier transform vector quantizer (FTVQ) uses a product code structure, providing different codes for different coefficient vectors corresponding to different frequency bands. This is a form of subband coding and yields a simple means of optimizing bit allocations among the subcodes. Two coding structures with corresponding distortion measures are considered: those that quantize vectors of pairs of real and imaginary coefficients and those that quantize separate vectors of magnitude and phase coefficients. Both structures yield good performance for the given complexity in comparison to waveform vector quantizers. For speech coding, a magnitude-phase FTVQ yields better subjective quality than a real-imaginary FTVQ when the rate allocation is properly chosen.     

Finite-state vector quantization for waveform coding

A finite-state vector quantizer is a finite-state machine used for data compression: Each successive source vector is encoded into a codeword using a minimum distortion rule, and into a code book, depending on the encoder state. The current state and the selected codeword then determine the next encoder state. A finite-state vector quantizer is capable of making better use of the memory in a source than is an ordinary memoryless vector quantizer of the same dimension or blocklength. Design techniques are introduced for finite-state vector quantizers that combine ad hoc algorithms with an algorithm for the design of memoryless vector quantizers. Finite-state vector quantizers are designed and simulated for Gauss-Markov sources and sampled speech data, and the resulting performance and storage requirements are compared with ordinary memoryless vector quantization.     

On algebraic soft-decision decoding algorithms for BCH codes

Three algebraic soft-decision decoding algorithms are presented for binary Bose-Chaudhuri-Hocquengham (BCH) codes. Two of these algorithms are based on the bounded distance (BD)+1 generalized minimum-distance (GMD) decoding presented by Berlekamp (1984), and the other is based on Chase (1972) decoding. A simple algebraic algorithm is first introduced, and it forms a common basis for the decoding algorithms presented. Next, efficient BD+1 GMD and BD+2 GMD decoding algorithms are presented. It is shown that, for binary BCH codes with odd designed-minimum-distance d and length n, both the BD+1 GMD and the BD+2 GMD decoding algorithms can be performed with complexity O(nd). The error performance of these decoding algorithms is shown to be significantly superior to that of conventional GMD decoding by computer simulation. Finally, an efficient algorithm is presented for Chase decoding of binary BCH codes. Like a one-pass GMD decoding algorithm, this algorithm produces all necessary error-locator polynomials for Chase decoding in one run     

Performance of quantizers on noisy channels using structuredfamilies of codes

Achievable distortion bounds are derived for the cascade of structured families of binary linear channel codes and binary lattice vector quantizers. It is known that for the cascade of asymptotically good channel codes and asymptotically good vector quantizers the end-to-end distortion decays to zero exponentially fast as a function of the overall transmission rate, and is achieved by choosing a channel code rate that is independent of the overall transmission rate. We show that for certain families of practical channel codes and binary lattice vector quantizers, the overall distortion can be made to decay to zero exponentially fast as a function of the square root of transmission rate. This is achieved by carefully choosing a channel code rate that decays to zero as the transmission rate grows. Explicit channel code rate schedules are obtained for several well-known families of channel codes     

具有身份识别功能的矢量地图数字水印研究

在某些重要应用领域,一旦地图资源非法泄露,确定地图来源是首要问题。在该文提出的方案中,首先采集地图所有者的指纹信息并进行特征提取,提取到的特征信息转换为二进制编码,并将该编码嵌入到矢量地图属性文件的对象定义数据块中。在对象定义块中,属性描述信息之后以结束符作为结束标识,结束符识之后存储的数据不被任何工具软件读取和显示。实验和分析表明,该隐藏算法具有较好的鲁棒性,能够对地图无损地嵌入和提取水印信息,NC值可达97%以上,兼顾结合指纹匹配算法的性能,身份识别的准确率保持在80%以上。     

A vector quantization approach to universal noiseless coding andquantization

A two-stage code is a block code in which each block of data is coded in two stages: the first stage codes the identity of a block code among a collection of codes, and the second stage codes the data using the identified code. The collection of codes may be noiseless codes, fixed-rate quantizers, or variable-rate quantizers. We take a vector quantization approach to two-stage coding, in which the first stage code can be regarded as a vector quantizer that “quantizes” the input data of length n to one of a fixed collection of block codes. We apply the generalized Lloyd algorithm to the first-stage quantizer, using induced measures of rate and distortion, to design locally optimal two-stage codes. On a source of medical images, two-stage variable-rate vector quantizers designed in this way outperform standard (one-stage) fixed-rate vector quantizers by over 9 dB. The tail of the operational distortion-rate function of the first-stage quantizer determines the optimal rate of convergence of the redundancy of a universal sequence of two-stage codes. We show that there exist two-stage universal noiseless codes, fixed-rate quantizers, and variable-rate quantizers whose per-letter rate and distortion redundancies converge to zero as (k/2)n ^-1 log n, when the universe of sources has finite dimension k. This extends the achievability part of Rissanen's theorem from universal noiseless codes to universal quantizers. Further, we show that the redundancies converge as O(n^-1) when the universe of sources is countable, and as O(n^-1+ϵ) when the universe of sources is infinite-dimensional, under appropriate conditions     

Linear-time encodable/decodable codes with near-optimal rate

We present an explicit construction of linear-time encodable and decodable codes of rate r which can correct a fraction (1-r-/spl epsiv/)/2 of errors over an alphabet of constant size depending only on /spl epsiv/, for every 00. The error-correction performance of these codes is optimal as seen by the Singleton bound (these are "near-MDS" codes). Such near-MDS linear-time codes were known for the decoding from erasures; our construction generalizes this to handle errors as well. Concatenating these codes with good, constant-sized binary codes gives a construction of linear-time binary codes which meet the Zyablov bound, and also the more general Blokh-Zyablov bound (by resorting to multilevel concatenation). Our work also yields linear-time encodable/decodable codes which match Forney's error exponent for concatenated codes for communication over the binary symmetric channel. The encoding/decoding complexity was quadratic in Forney's result, and Forney's bound has remained the best constructive error exponent for almost 40 years now. In summary, our results match the performance of the previously known explicit constructions of codes that had polynomial time encoding and decoding, but in addition have linear-time encoding and decoding algorithms.     

Two Bit-Flipping Decoding Algorithms for Low-Density Parity-Check Codes

In this letter, a low complexity decoding algorithm for binary linear block codes is applied to low-density paritycheck (LDPC) codes and improvements are described, namely an extension to soft-decision decoding and a loop detection mechanism. For soft decoding, only one real-valued addition per code symbol is needed, while the remaining operations are only binary as in the hard decision case. The decoding performance is considerably increased by the loop detection. Simulation results are used to compare the performance with other known decoding strategies for LDPC codes, with the result that the presented algorithms offer excellent performances at smaller complexity.     

Side match and overlap match vector quantizers for images

A class of vector quantizers with memory that are known as finite state vector quantizers (FSVQs) in the image coding framework is investigated. Two FSVQ designs, namely side match vector quantizers (SMVQs) and overlap match vector quantizers (OMVQs), are introduced. These designs take advantage of the 2-D spatial contiguity of pixel vectors as well as the high spatial correlation of pixels in typical gray-level images. SMVQ and OMVQ try to minimize the granular noise that causes visible pixel block boundaries in ordinary VQ. For 512 by 512 gray-level images, SMVQ and OMVQ can achieve communication quality reproduction at an average of 1/2 b/pixel per image frame, and acceptable quality reproduction. Because block boundaries are less visible, the perceived improvement in quality over ordinary VQ is even greater. Owing to the structure of SMVQ and OMVQ, simple variable length noiseless codes can achieve as much as 60% bit rate reduction over fixed-length noiseless codes.     

Complexity Reduction in SISO Decoding of Block Codes

SISO decoding for block codes can be carried out based on a trellis representation of the code. However, the complexity entailed by such decoding is most often prohibitive and thus prevents practical implementation. This paper examines a new decoding scheme based on the soft-output Viterbi algorithm (SOVA) applied to a sectionalized trellis for linear block codes. The computational complexities of the new SOVA decoder and of the conventional SOVA decoder, based on a bit-level trellis, are theoretically analyzed and derived for different linear block codes. These results are used to obtain optimum sectionalizations of a trellis for SOVA. For comparisons, the optimum sectionalizations for Maximum A Posteriori (MAP) and Maximum Logarithm MAP (Max-Log-MAP) algorithms, and their corresponding computational complexities are included. The results confirm that the new SOVA decoder is the most computationally efficient SISO decoder, in comparisons to MAP and Max-Log-MAP algorithms. The simulation results of the bit error rate (BER) performance, assuming binary phase -- shift keying (BPSK) and additive white Gaussian noise (AWGN) channel, demonstrate that the performance of the new decoding scheme is not degraded. The BER performance of iterative SOVA decoding of serially concatenated block codes shows no difference in the quality of the soft outputs of the new decoding scheme and of the conventional SOVA.     

Channel-Optimized Quantization With Soft-Decision Demodulation for Space–Time Orthogonal Block-Coded Channels

We introduce three soft-decision demodulation channel-optimized vector quantizers (COVQs) to transmit analog sources over space–time orthogonal block (STOB)-coded flat Rayleigh fading channels with binary phase-shift keying (BPSK) modulation. One main objective is to judiciously utilize the soft information of the STOB-coded channel in the design of the vector quantizers while keeping a low system complexity. To meet this objective, we introduce a simple space–time decoding structure that consists of a space–time soft detector, followed by a linear combiner and a scalar uniform quantizer with resolution$q$. The concatenation of the space–time encoder/modulator, fading channel, and space–time receiver can be described by a binary-input,$2^q$-output discrete memoryless channel (DMC). The scalar uniform quantizer is chosen so that the capacity of the equivalent DMC is maximized to fully exploit and capture the system's soft information by the DMC. We next determine the statistics of the DMC in closed form and use them to design three COVQ schemes with various degrees of knowledge of the channel noise power and fading coefficients at the transmitter and/or receiver. The performance of each quantization scheme is evaluated for memoryless Gaussian and Gauss–Markov sources and various STOB codes, and the benefits of each scheme is illustrated as a function of the antenna-diversity and soft-decision resolution$q$. Comparisons to traditional coding schemes, which perform separate source and channel coding operations, are also provided.     

A* decoding of block codes

The A* algorithm is applied to maximum-likelihood soft-decision decoding of binary linear block codes. This paper gives a tutorial on the A* algorithm, compares the decoding complexity with that of exhaustive search and Viterbi decoding algorithms, and presents performance curves obtained for several codes     

一种基于八叉树的Huffman解码方法及其在MPEG-4中的应用

传统的二值Huffman解码方法的解码效率较低。为了提高解码速度,该文提出了一种基于八叉树的Huffman解码方法。该方法将Huffman码表示为八叉树结构,并根据各个节点在树中的位置将码表重建为一维数组。解码时,每次从码流中读取3 bit码元,并使用数值计算代替判断和跳转操作,从而提高了解码效率。将本文方法应用于MPEG-4 VLC和RVLC解码的实验结果表明,该方法在内存增加不大的情况下能大幅度提高Huffman解码效率,其性能优于其它方法。     

Soft decision decoding of Reed-Solomon codes

This paper presents a maximum-likelihood decoding (MLD) and a suboptimum decoding algorithm for Reed-Solomon (RS) codes. The proposed algorithms are based on the algebraic structure of the binary images of RS codes. Theoretical bounds on the performance are derived and shown to be consistent with simulation results. The proposed suboptimum algorithm achieves near-MLD performance with significantly lower decoding complexity. It is also shown that the proposed suboptimum, algorithm has better performance compared with generalized minimum distance decoding, while the proposed MLD algorithm has significantly lower decoding complexity than the well-known Vardy-Be'ery (1991) MLD algorithm.