Turbo乘积码构造方法的研究

Turbo乘积码因其具有接近香农限的译码性能和适合高速译码的并行结构,已成为纠错编码领域的研究热点。Turbo乘积码的分量码一般由扩展汉明码构造而成,所以该类码字编码和译码的硬件实现比较简单。当Turbo乘积码采用扩展汉明码作为子码时,随着信噪比的提高,码字的最小码重对误帧率的影响会逐步增大。文中改进了Turbo乘积码编码结构,在只增加较小的编译码复杂度和时延的情况下,提高了码字的最小码重,并减少了最小码重码字在码字空间所占的比例。通过仿真和分析,比较了这种码和TPC码在误帧率性能、码字的最小码重分布以及最小码间距估计上的差异。     

Rate Variable, Multi-Binary Turbo Codes with Controlled Error-Floor

In this letter we propose rate variable turbo codes based on the parallel concatenation of tailbiting Recursive Systematic multi-binary (m-ary) convolutional codes. Rate variability is not achieved by puncturing, which can have adverse effects on the minimum distance of the code. Using a variable number of input lines of the encoder, we obtain several different overall rates ranging from 1/2 to 7/8. The most suitable Soft-In- Soft-Out decoding algorithm for these turbo codes is based on the Dual Reciprocal Code, which is very efficient for high rate codes. A particular interleaver design, namely the ?backbone? interleaver, guarantees a high Hamming weight in codewords with information weight 2 and 3, as well as good minimum distances and fairly low multiplicities for higher information weights. Therefore, these codes have very low error floors.     

Coherent网络中的纠错码

网络编码对网络中的传输错误或恶意攻击十分敏感,如果网络拓扑和网络码对于网络的收点和发点都是已知的,这种类型的网络称为Coherent网络。在Coherent网络中,网络汉明重量的概念拉近了网络纠错码和传统纠错码之间的距离,传统纠错码的一些理论和方法有望在将来应用于网络纠错码。类似于传统纠错码,极小距离反映了网络纠错码的纠错能力。利用陪集码理论去描述和研究网络纠错码是一个令人感兴趣的研究方向。     

Lattice constellations and codes from quadratic number fields

We propose new classes of linear codes over integer rings of quadratic extensions of Q, the field of rational numbers. The codes are considered with respect to a Mannheim metric, which is a Manhattan metric module a two-dimensional (2-D) grid, in particular, codes over Gaussian integers and Eisenstein-Jacobi integers are extensively studied. Decoding algorithms are proposed for these codes when up to two coordinates of a transmitted code vector are affected by errors of arbitrary Mannheim weight. Moreover, we show that the proposed codes are maximum-distance separable (MDS), with respect to the Hamming distance. The practical interest in such Mannheim-metric codes is their use in coded modulation schemes based on quadrature amplitude modulation (QAM)-type constellations, for which neither the Hamming nor the Lee metric is appropriate     

Stacking techniques for linear codes

A procedure for subspace stacking is proposed, and it is proved that the technique is equally successful for both linear codes and anticodes. It is demonstrated that families of errorcorrecting codes may be constructed using the proposed technique for stacking linear codes. Examples of such codes are given with rates better than the best known codes of identical Hamming distance and the same number of information digits.     

On block codes with specified maximum distance (Corresp.)

A new class of block codes with specified length and maximum Hamming distance between the codewords is given. It is also shown that the proposed codes have the largest number of words when the maximum Hamming distance specified is 1, 2, or 3.     

A family of low-complexity binary linear codes for Bluetooth and BLAST signaling applications

We construct a family of linear binary block codes that are useful for Bluetooth, OFDM and BLAST applications. These codes are derived from ordinary block repetition codes using cyclic shifts of the input information vector which greatly simplifies encoding. We find several sets of cyclic shifts that constrain the search for good codes. We consider code lengthening and the input-output weight enumerators. We show that the codes are good candidates for low-power, low-cost and high data-rate applications using fixed code rate and variable codeword length, or adaptive coding with variable minimum Hamming distance. We propose a parallel structure of the encoder well-suited to OFDM and BLAST systems. Finally, we give an example of code design for use in retransmission schemes, and another example of a concatenated rate 2/3 code well-suited to the Bluetooth system.     

Construction of type-II QC-LDPC codes with fast encoding based on perfect cyclic difference sets

In view of the problems that the encoding complexity of quasi-cyclic low-density parity-check (QC-LDPC) codes is high and the minimum distance is not large enough which leads to the degradation of the error-correction performance, the new irregular type-II QC-LDPC codes based on perfect cyclic difference sets (CDSs) are constructed. The parity check matricesof these type-II QC-LDPC codes consist of the zero matrices with weight of 0, the circulant permutation matrices (CPMs) with weight of 1 and the circulant matrices with weight of 2 (W2CMs). The introduction of W2CMs in parity check matrices makes it possible to achieve the larger minimum distance which can improve the error-correction performance of the codes. The Tanner graphs of these codes have no girth-4, thus they have the excellent decoding convergence characteristics. In addition, because the parity check matrices have the quasi-dual diagonal structure, the fast encoding algorithm can reduce the encoding complexity effectively. Simulation results show that the new type-II QC-LDPC codes can achieve a more excellent error-correction performance and have no error floor phenomenon over the additive white Gaussian noise (AWGN) channel with sum-product algorithm (SPA) iterative decoding.     

The Z4-linearity of Kerdock, Preparata, Goethals, andrelated codes

Certain notorious nonlinear binary codes contain more codewords than any known linear code. These include the codes constructed by Nordstrom-Robinson (1967), Kerdock (1972), Preparata (1968), Goethals (1974), and Delsarte-Goethals (1975). It is shown here that all these codes can be very simply constructed as binary images under the Gray map of linear codes over Z₄, the integers mod 4 (although this requires a slight modification of the Preparata and Goethals codes). The construction implies that all these binary codes are distance invariant. Duality in the Z₄ domain implies that the binary images have dual weight distributions. The Kerdock and “Preparata” codes are duals over Z₄-and the Nordstrom-Robinson code is self-dual-which explains why their weight distributions are dual to each other. The Kerdock and “Preparata” codes are Z₄-analogues of first-order Reed-Muller and extended Hamming codes, respectively. All these codes are extended cyclic codes over Z₄, which greatly simplifies encoding and decoding. An algebraic hard-decision decoding algorithm is given for the “Preparata” code and a Hadamard-transform soft-decision decoding algorithm for the I(Kerdock code. Binary first- and second-order Reed-Muller codes are also linear over Z₄ , but extended Hamming codes of length n⩾32 and the Golay code are not. Using Z₄-linearity, a new family of distance regular graphs are constructed on the cosets of the “Preparata” code     

基于旋转因子的差分酉空时分组码

基于TBH和Jafarkhan编码方案的两组准正交空时分组码,引入自适应旋转因子构造出四种差分调制酉矩阵,该方法不仅没有带来星座扩展,还使新的码字具有较大的欧氏距离。同时在接收端基于角度算子,形成了简化的成对译码方法。仿真结果表明：尽管此设计方法增加了一定的复杂度,但它比没有加入旋转因子的差分酉空时分组码具有更好的误码性能。     

Reducible rank codes and their applications to cryptography

We present a new family of so-called reducible rank codes which are a generalization of rank product codes . This family includes maximal rank distance (MRD) codes for lengths n>N in the field F/sub N/. We give methods for encoding and decoding reducible rank codes. A public key cryptosystem based on these codes and on the idea of a column scrambler is proposed. The column scrambler "mixes" columns of a generator (parity-check) matrix of a code. It makes the system more resistant to structural attacks such as Gibson's attacks. Possible attacks on the system are thoroughly studied. The system is found to be secure against known attacks for public keys of about 16 kbits and greater.     

Improved coding techniques for preceded partial-response channels

A coset of a convolutional code may be used to generate a zero-run length limited trellis code for a 1-D partial-response channel. The free squared Euclidean distance, d_free², at the channel output is lower bounded by the free Hamming distance of the convolutional code. The lower bound suggests the use of a convolutional code with maximal free Hamming distance, d_max(R,N), for given rate R and number of decoder states N. In this paper we present cosets of convolutional codes that generate trellis codes with d_free ²>d_max(R,N) for rates 1/5⩽R⩽7/9 and (d _free²=d_max(R,N) for R=13/16,29/32,61/64, The tabulated convolutional codes with R⩽7/9 were not optimized for Hamming distance. Instead, a computer search was used to determine cosets of convolutional codes that exploit the memory of the 1-D channel to increase d_free² at the channel output. The search was limited by only considering cosets with certain structural properties. The R⩾13/16 codes were obtained using a new construction technique for convolutional codes with free Hamming distance 4. Newly developed bounds on the maximum zero-run lengths of cosets were used to ensure a short maximum run length at the 1-D channel output     

Trellis Coding for Partial-Response Channels

We consider trellis-coding techniques for improving the reliability of digital transmission over noisy partial-response channels. Such channels are commonly encountered in digital communication systems, and also play a role in devices for data recording. Concentrating on the channels with characteristics(1 mp D), we study methods to obtain codes which increase free Euclidean distance between permitted sequences of channel outputs and avoid the occurrence of unlimited runs of identical outputs at the expense of some loss in data rate. One technique employs the concept of set partitioning. The other is based on using convolutional codes designed for maximum free Hamming distance in conjunction with a precoder. Both methods lead to essentially equivalent codes.     

Binary codes with disjoint codebooks and mutual Hamming distance

Equal-length linear binary block error-control codes with disjoint codebooks and mutual Hamming distance are considered. A method of constructing pairs of these disjoint codes from known cyclic codes, and determining their mutual distance, is described. Some sets of length-15 cyclic codes are tabulated.     

Estimating the fraction of erasure patterns correctable by linear codes

The conditional probability (fraction) of the successful decoding of erasure patterns of high (greater than the code distance) weights is investigated for linear codes with the partially known or unknown weight spectra of code words. The estimated conditional probabilities and the methods used to calculate them refer to arbitrary binary linear codes and binary Hamming, Panchenko, and Bose–Chaudhuri–Hocquenghem (BCH) codes, including their extended and shortened forms. Error detection probabilities are estimated under erasure-correction conditions. The product-code decoding algorithms involving the correction of high weight erasures by means of component Hamming, Panchenko, and BCH codes are proposed, and the upper estimate of decoding failure probability is presented.     

功耗分析攻击中的功耗与数据相关性模型

在对密码设备进行功耗分析攻击时,攻击者需要建立密钥或者与密钥关联的数据值与被攻击设备的功耗相关性模型,藉此通过对功耗的分析破解出敏感信息。从攻击者的角度对器件功耗物理特性分析的基础上,重构了汉明距离模型和汉明重量模型,并从理论上证明了汉明重量模型的正确性,并建立起MCU功耗采集平台,验证了汉明重量模型的有效性和实用性。     

Test data compression using alternating variable run-length code

This paper presents a unified test data compression approach, which simultaneously reduces test data volume, scan power consumption and test application time for a system-on-a-chip (SoC). The proposed approach is based on the use of alternating variable run-length (AVR) codes for test data compression. A formal analysis of scan power consumption and test application time is presented. The analysis showed that a careful mapping of the don’t-cares in pre-computed test sets to 1s and 0s led to significant savings in peak and average power consumption, without requiring slower scan clocks. The proposed technique also reduced testing time compared to a conventional scan-based scheme. The alternating variable run-length codes can efficiently compress the data streams that are composed of both runs 0s and 1s. The decompression architecture was also presented in this paper. Experimental results for ISCAS'89 benchmark circuits and a production circuit showed that the proposed approach greatly reduced test data volume and scan power consumption for all cases.     

Provably Good Codes for Hash Function Design

A new technique to lower-bound the minimum distance of certain types of quasi-cyclic codes with large dimension by reducing the problem to lower-bounding the minimum distance of a few significantly smaller codes has been developed. These codes have the property that they have extremely efficient software encoders. Using this technique, it is proved that a code which is similar to the SHA-1 (Secure Hash Algorithm, to be explained shortly) message expansion code has minimum distance $82$, and that too in just the last 64 of the 80 expanded words. In fact, the proposed code has much greater distance than that of SHA-1 code, which makes our proposed hashing scheme robust against cryptographic attacks. The technique is further used to find the minimum weight of the SHA-1 code itself (25 in last 60 words), which was an open problem. Estimating minimum distance of a code given by its parity-check matrix is well known to be a hard problem. Our technique is expected to be helpful in estimating minimum distance of similar codes as well as in designing future practical cryptographic hash functions.      

Decoding algorithm and architecture for BCH codes under the Lee Metric

The Lee metric measures the circular distance between two elements in a cyclic group and is particularly appropriate as a measure of distance for data transmission under phase-shift-keying modulation over a white noise channel. In this paper, using newly derived properties on Newton?s identities, we initially investigate the Lee distance properties of a class of BCH codes and show that (for an appropriate range of parameters) their minimum Lee distance is at least twice their designed Hamming distance. We then make use of properties of these codes to devise an efficient algebraic decoding algorithm that successfully decodes within the above lower bound of the Lee error-correction capability. Finally, we propose an attractive design for the corresponding VLSI architecture that is only mildly more complex than popular decoder architectures under the Hamming metric; since the proposed architecture can also be used for decoding under the Hamming metric without extra hardware, one can use the proposed architecture to decode under both distance metrics (Lee and Hamming).     

Structured set partitions and multilevel concatenated coding forpartial response channels

We present a systematic way to construct multilevel concatenated codes for partial response (PR) channels using: (1) a structured set partition (SSP) of multiple channel output sets and (2) a set of conventional block codes with different error correcting capabilities. A lower bound on the minimum squared Euclidean distance of the constructed codes is given. This bound is based on the interset minimal Euclidean distances of the SSP and the minimum Hamming distances of the used block codes. An example of SSP for the extended class 4 partial response channel (EPR4) is presented. Iterative suboptimal decoding, which combines Viterbi detection on the trellis of the PR channel with algebraic error detection/correction, can be applied to the constructed concatenated codes. Truncated versions of the iterative decoding scheme are simulated and compared with each other