Optimal correction of concatenated fault-tolerant quantum codes

We present a method of concatenated quantum error correction in which improved classical processing is used with existing quantum codes and fault-tolerant circuits to more reliably correct errors. Rather than correcting each level of a concatenated code independently, our method uses information about the likelihood of errors having occurred at lower levels to maximize the probability of correctly interpreting error syndromes. Results of simulations of our method applied to the [[4,1,2]] subsystem code indicate that it can correct a number of discrete errors up to half of the distance of the concatenated code, which is optimal.     

ADJACENT-ERROR CORRECTING BINARY PERFECT CODES

Abstract

A new type of codes that correct only a given number of adjacent errors in the binary case have been introduced in this paper. These codes are adjacent-error correcting perfect and form a doubly infinite class, i.e., for a given number of adjacent errors these exist for different lengths as also for different number of adjacent errors these can be developed for specific lengths.     

Secret sharing schemes from binary linear codes

In principle, every linear code can be used to construct a secret sharing scheme. However, in general, determining the access structure of the scheme is very hard. On the other hand, finding error correcting codes that produce secret sharing schemes with efficient access structures is also difficult. In this paper, we study a set of minimal codewords for certain classes of binary linear codes, and then determine the access structure of secret sharing schemes based on these codes. Furthermore, we prove that the secret sharing schemes obtained are democratic in the sense that every participant is involved in the same number of minimal access sets.     

纠错编码在无线局域网中的应用研究

介绍纠错编码原理,着重介绍几种纠错编码例如线性分组码、卷积码、级联码,同时介绍无线网络传输的特点,无线传输中误码产生的主要原因。结合这两点,介绍在无线局域网中采用的纠错编码方式,编码纠正错误对于帧错误概率和吞吐都有改善作用,在特定的误码率条件下吞吐量有显著的提高。     

Low-density parity-check codes based on steiner systems and permutation matrices

An algorithm for generating parity-check matrices of regular low-density paritycheck codes based on permutation matrices and Steiner triple systems S(v, 3, 2), v = 2 ^m ? 1, is proposed. Estimations of the rate, minimum distance, and girth for obtained code constructions are presented. Results of simulation of the obtained code constructions for an iterative “belief propagation” (Sum-Product) decoding algorithm applied in the case of transmission over a binary channel with additive Gaussian white noise and BPSK modulation are presented.     

Bh序列和Magnitude错误标准下m元纠错码构造

文献对Bh序列和Magnitude错误标准下m元t-sEC/AUED码的关系进行了讨论,在此基础上提出了一种Magnitude错误标准下m元可纠t个对称错的纠错码的构造方法,并相应地给出了可纠t个对称错的纠错码码字个数的下界。     

Self-checking circuits and decoding algorithms for binary hamming and BCH codes and Reed-Solomon codes over GF(2 m )

We consider problems of detecting errors in combinational circuits and algorithms for the decoding of linear codes. We show that a totally self-checking combinatorial circuit for the decoding of a binary Hamming [n, k] code can be constructed if and only if n = 2 ^r ? 1, r = n?k. We introduce the notion of a totally self-checking combinational circuit detecting error clusters of size at most µ; for shortened Hamming [n,k] codes, we construct totally self-checking decoding combinational circuits detecting error clusters of size at most µ, 2 ≤ µ < n?k. We describe single-error protected and self-checking algorithms: the extended Euclidean algorithm and decoding algorithms for binary BCH codes and Reed-Solomon codes over GF(2 ^m ).     

基于全局距离最优的抗污染极短纠错码设计

针对现有二维码在复杂环境中抗污染能力弱、解码速度慢的问题,提出了一种基于全局距离最优的抗污染极短纠错码。首先,构建了表征污染环境的凹凸多边形数学模型;然后,设计了采用3个编码点表示一个目标数据位的极短纠错码;最后,设计了在有限约束域内全局距离最优的编码点的编排方法,并给出了对应的解码算法。对极短纠错码的抗污染能力和识别速度进行了仿真评估,并与经典的BCH码进行了对比。结果表明,当目标数据长度为18、编码点数为63时,极短纠错码在同等污染环境中识别准确率接近BCH码,而解码速度是BCH码的130倍。所提编码还具有结构简洁明确、编码点数适应能力强、易于标准化推广应用等显著优点。     

Detecting and Correcting Capabilities of Convolutional Codes

A convolutional code can be used to detect or correct infinite sequences of errors or to correct infinite sequences of erasures. First, erasure correction is shown to be related to error detection, as well as error detection to error correction. Next, the active burst distance is exploited, and various bounds on erasure correction, error detection, and error correction are obtained for convolutional codes. These bounds are illustrated by examples.     

Quantum Error Correction of Time-correlated Errors

The complexity of the error correction circuitry forces us to design quantum error correction codes capable of correcting a single error per error correction cycle. Yet, time-correlated error are common for physical implementations of quantum systems; an error corrected during the previous cycle may reoccur later due to physical processes specific for each physical implementation of the qubits. In this paper, we study quantum error correction for a restricted class of time-correlated errors in a spin-boson model. The algorithm we propose allows the correction of two errors per error correction cycle, provided that one of them is time-correlated. The algorithm can be applied to any stabilizer code when the two logical qubits and are entangled states of 2 ⁿ basis states in .      

Decoding turbo-like codes via linear programming

We introduce a novel algorithm for decoding turbo-like codes based on linear programming. We prove that for the case of repeat-accumulate codes, under the binary symmetric channel with a certain constant threshold bound on the noise, the error probability of our algorithm is bounded by an inverse polynomial in the code length.Our linear program (LP) minimizes the distance between the received bits and binary variables representing the code bits. Our LP is based on a representation of the code where codewords are paths through a graph. Consequently, the LP bears a strong resemblance to the min-cost flow LP. The error bounds are based on an analysis of the probability, over the random noise of the channel, that the optimum solution to the LP is the path corresponding to the original transmitted codeword.     

基于证据理论的纠错输出编码解决多类分类问题

针对多类分类问题,利用纠错输出编码作为分解框架,把多类问题转化为多个二类问题加以解决;同时提出一种基于证据理论的解码策略,把每一个二分器的输出作为证据之一进行融合,并讨论在两种编码类型(二元和三元编码矩阵)下证据融合的不同策略.通过实验分别对UCI数据集和3种一维距离像数据集进行测试,并与几种经典的解码方法进行比较,验证了所提出的方法能有效提高纠错输出编码特别是三元编码矩阵的分类正确率.     

On level-weight studies of binary and m-ary gray codes

Gray codes are useful in the minimization of digital errors due to an ambiguous analog signal between two adjacent levels. The weight structure in coding has its own significance. In this paper, we study the weight structure of the binary Gray code G_n⁽⁰⁾ and extend the result for nonbinary Gray codes G_m:n⁽⁰⁾. With our study it is possible to find the weight of a codeword occupying a given place in the codebook.     

一种新的无损图像压缩算法的研究

提出了新的二进制(位级)无损图像压缩方法——将错误纠正BCH码引入到图像压缩算法中;将图像的二进制分为大小为7的码字,这些块进入到BCH解码器,消除了校验位后,使得原来的块的大小减少到4位。实验结果表明,此压缩算法是有效的,并给出了一个很好的压缩比,而且不丢失数据。BCH码的使用在提高压缩比方面比单纯霍夫曼压缩的结果要好。     

一种基于随机序列的数字指纹编码和跟踪算法

基于二进制随机编码技术,提出了一种简洁有效的合谋容忍数字指纹编码和跟踪算法.从理论上推导了算法的编码长度、合谋人数以及跟踪算法错误概率之间的关系,给出了错误概率界.在不同的应用场合,对于给定的任意小的错误概率,可以通过适当选取编码长度,使得在抗一定合谋攻击强度的情况下,错误概率满足应用要求.相对于已有的二进制随机编码指纹算法,在同样的错误概率下,本算法的数字指纹编码长度得到有效缩短.     

Efficient dynamic priority based soft error mitigation techniques for configuration memory of FPGA hardware

Radiation-induced single bit upsets (SBUs) and multi-bit upsets (MBUs) are more prominent in Field Programmable Gate Arrays (FPGAs) due to the presence of a large number of latches in the configuration memory (CM) of FPGAs. At the same time, SBUs and MBUs in the CM can permanently or temporarily affect the hardware circuit implemented on FPGA. Hence, error mitigation and recovery techniques are necessary to protect the FPGA hardware from permanent faults arising due to such SBUs and MBUs. Different existing techniques used to mitigate the effect of soft errors in FPGA have high overhead and their implementations are also quite complex. In this paper, we have proposed efficient single bit as well as multi-bit error correcting methods to correct errors in the CM of FPGAs using simple parity equations and Erasure code. These codes are easy to implement, and the needed decoding circuits are also simple. Use of Dynamic Partial Reconfiguration (DPR) along with a simple hardware scheduling algorithm based download manager helps to perform the error correction in the CM without suspending the operations of the other hardware blocks. We propose a first of its kind methodology for novel transient fault correction using efficient error correcting codes with hardware scheduling for FPGAs. To validate the design we have tested the proposed methodology with Kintex FPGA. We have also measured different parameters like fault recovery time, power consumption, resource overhead and error correction efficiency to estimate the performance of our proposed methods.     

Blind parameter estimation of turbo convolutional codes: Noisy and non-synchronized scenario

Blind estimation of forward error correction code parameters at the receiver plays a significant role in non-cooperative communication, adaptive modulation and coding systems, and reconfigurable receiver systems. Turbo convolutional codes, a parallel concatenation of multiple convolutional codes, are used in digital communication and storage systems to achieve low bit error rate. The present paper proposes innovative algorithms for the blind estimation of code parameters and reconstruction of turbo convolutional encoder over noisy scenario. The turbo convolutional code is designed using two component codes along with an interleaver. Recursive systematic convolutional codes are used as component codes. Any imperfection in synchronization of received data for the proposed code parameter estimation algorithm is compensated through a bit position adjustment parameter. The performance of the proposed algorithms in terms of parameter estimation accuracy is investigated for different modulation order, code rate, and constraint length values. It is observed that the performance improves with decrease in modulation order and constraint length values.     

Optimisation of multiclass supervised classification based on using output codes with error-correcting

An approach of solving the problem of multiclass supervised classification, based on using errorcorrecting codes is considered. The main problem here is the creation of binary code matrix, which provides high classification accuracy. Binary classifiers must be distinct and accurate. In this issue, there are many questions. What should be the elements of the matrix, how many elements provide the best accuracy and how to find them? In this paper an approach to solve some optimization problems for the construction of the binary code matrix is considered. The problem of finding the best binary classifiers (columns of matrix) is formulated as a discrete optimization problem. For some partial precedent classification approach, there is a calculation of the effective values of optimising function. Prospects of this approach are confirmed by a series of experiments on various practical tasks.     

基于矩阵模型的线性分组码及分组交织识别

针对通信系统中错误不可避免的现状,在矩阵分析法的基础上,提出反向纠错思想。利用穷举法,穷举条件规定范围内所有可能的分组码和分组交织模式,在纠错译码后再进行判定,得出正确的交织参数。对该方法在不同的误码率条件下进行仿真,得出能够正确识别的误码范围。     

距离为6的二元自对偶码的子码

用随机搜索算法研究了码长n满足22≤n≤30且距离为6的二元自对偶码的子码,构造出它们的对偶距离为3、4、5和6的子码的生成矩阵。研究了这些子码构成的码链以及它们的对偶码构成的码链。利用所得到的码链,由Steane构造法构造出距离为5和6的具有很好参数的量子纠错码,改进了前人得到的几个量子纠错码的参数。