基于随机置换展开与停止集的LT码联合编译码算法

针对短码长LT码(码长在103以下)的随机编码方式,需要较高的编码冗余才能保证一定的译码性能的问题。设计了一种基于限制Tanner图连接边随机关系的随机置换展开编码算法,可以实现在较小编码冗余开销下提高短码长LT码的可译码概率。在此基础上,针对短码长LT码的传统BP译码算法效率不高的问题,充分利用BP算法译码失败的停止集剩余信息,设计了采用上述编码算法的短码长LT码的停止集高斯译码算法,可以获得接近最大似然译码的性能。仿真结果表明,所提出的编译码联合算法有效降低了短码长LT码满足10 4译码失败概率时所需的编码冗余开销。     

Optimized parallel decoding of difference set codes for high speed memories

The interest in using advanced Error Correction Codes (ECCs) to protect memories and caches is growing. This is because as process technology downscales, errors are more frequent and also tend to affect multiple bits. For SRAM memories and caches, latency is a limiting factor and ECCs have to provide low decoding times that can in most cases be only achieved with the use of a parallel decoder. One important issue with parallel decoders is that they typically require large circuit area to be implemented. One type of ECCs that has been explored for memory protection is Difference Set (DS) codes. In this research note, an optimized parallel decoding scheme for DS codes is presented and evaluated. The results show that the circuit area and the decoding delay are reduced compared to a traditional implementation. In addition, the new scheme enables a reduction in the number of parity check bits thus reducing the memory size.     

无速率编码及其应用综述

纠错编码技术通过引入冗余增加可靠性,是现代通信的关键技术之一。无速率编码是一类新兴纠错编码,其速率可以根据信道状态自适应改变,编译码算法较为简单,且性能优异,可以适用于不同的应用场景,因此受到了国内外学者和工业界的关注。介绍了4种经典或新兴的无速率编码方案,包括卢比变换(Luby Transform,LT)码、Raptor码、在线喷泉码(OFC)和BATS(Batched Sparse)码。介绍无速率编码的基本原理,通过其发展过程比较不同无速率编码的特点。阐述了这些无速率编码的编译码方法,并简要介绍其最新的研究进展。最后,介绍无速率编码在广播通信及不等差保护、无线传感器网络、车联网、存储以及分布式计算等新老场景中的应用。无速率编码是一种复杂度低、灵活度高的编码,随着新型无速率编码的发展,在未来的分布式系统等场景中将会有更广泛的应用。     

Design of a soft-error robust microprocessor

The costs to protect a commercial microprocessor against soft errors are discussed in this work. Based on hardware and time redundancies, a protection scheme was designed at RT level to mitigate transient faults on combinational and memory circuits. A fault-tolerant IC version of a mass-produced 8-bit microprocessor is protected by the scheme. Design issues and results in area, performance and power are presented comparing the robust microprocessor with its non-protected version. The costs by flip-flop are also discussed permitting to estimate the overheads in area for any architecture. Furthermore, the RT-level protection scheme is compared with an electrical-level scheme based on a non-standard gate.     

基于一种交织码的多位翻转容错技术研究

随着技术的发展和核心电压的降低,存储器更易受瞬时错误（软错误）影响,成为影响航天器件可靠性的主要原因。错误检测与纠正（EDAC）码（也称错误纠正码）常用来对SRAM型存储器中的瞬时错误进行纠正,由单个高能粒子引起的多位翻转错误（SEMU）是普通纠一检二（SEC-DED）编码所无法处理的。提出了一种交织度为2的(26,16)交织码,该码由两个能纠正一位随机错误、二位突发错误的(13,8)系统码组成,(26,16)交织码能够纠正单个码字中小于二位的随机错误和小于四位突发错误（DEC-QAEC）。通过理论分析和硬件平台实验表明,该交织码在存储资源占用率、实时性相当情况下可靠性优于同等长度的SEC DED码,能有效提高SRAM型存储器抗多位翻转错误的能力。      

Improved online fountain codes based on shaping for left degree distribution

In this paper, an improved encoding scheme for online fountain codes is proposed with the joint optimization of variable node degree and check node degree is proposed. The coding scheme can be divided into the build-up phase and the completion phase. In the build-up phase, left degree distribution is exploited to guarantee optimal performance phase by modifying the traditional coding scheme of choosing input symbols uniformly at random. A memory-based selecting of the source symbols is employed to decrease the number of connected components, which can thus produce the dimension increasement of the linear subspace of a decoding graph constructed in the build-up phase. The upper bound on coding overhead is also derived from the analysis of random graph theory. Compared with conventional online fountain codes, it can be seen from the simulation results that the proposed scheme can provide significant performance improvement with respect to both coding overhead and feedback cost. Moreover, the lower encoding/decoding complexities may make the proposed scheme more practical in energy-constrained applications such as distributed storage.     

一种三容错数据布局

随着存储介质的增多,单容错、双容错的数据布局方案已经无法满足现有分布式存储系统对可靠性要求。该文在双容错行对角奇偶校验(Row Diagonal Parity, RDP)码的基础上,提出一种新的扩展行对角奇偶校验 (Extending Row Diagonal Parity, E-RDP)码,能够容许任何3存储节点出错,具有最大距离可分(Maximum Distance Separable, MDS)编码特性,冗余率与纠错能力达到3容错编码最优。并采用不同斜率几何直线图描述编译码过程,给出了一种快速译码算法,易于软硬件实现。与其它纠删码数据布局方案进行比较,理论分析结果表明,E-RDP码的空间利用率、编译码效率、小写性能以及平衡性的综合性能达到最优,具有实用价值。     

低复杂度的LDPC码联合编译码构造方法研究

LDPC码因为其具有接近香农限的译码性能和适合高速译码的并行结构,已经成为纠错编码领域的研究热点。LDPC码校验矩阵的构造是基于稀疏的随机图,所以该类码字编码和译码的硬件实现比较复杂。以单位阵的循环移位阵为基本单元,构造LDPC码的校验矩阵,降低了LDPC码在和积算法下的译码复杂度。同时考虑到LDPC码的编码复杂度,给出了一种可以简化编码的结构。针对该方案构造的LDPC码,提出了消除其二分图上的短圈的方法。通过大量的仿真和计算分析,本文比较了这种LDPC码和随机构造的LDPC码在误码率性能,圈长分布以及最小码间距估计上的差异。     

Functional testing of EPROMs

The aim of this paper is to develop a testing scheme for EPROM memories. The starting point is the assumed general model of EPROM memory logic structure. For this model, an adequate fault model is developed. The class of faults taken into consideration includes faults in input-output buffers, faults in address decoding circuitry, and faults in memory cell arrays. The proposed testing scheme makes possible the detection of all faults included in the assumed fault model. This scheme takes into account technological and economic aspects. The method proposed is illustrated by detailed solutions for the 2716 EPROM memory.     

RS regenerating codes for cloud storage fault-tolerant system

RS(Reed-Solomon) regenerating erasure codes was proposed for cloud storage fault-tolerant system,which not only inherited the reliability of the RS encoding,but also achieved the high efficiency of tolerance three faults.Hybrid recovery method of the single fault node based on RS regenerating erasure codes was introduced.And the theoretical lower bound of the number of accessing disks was computed.In theory,the performance evaluation of the storage overhead,decoding efficiency,and repair bandwidth of the RS regenerating erasure codes was carried out.Experiments results show that the repair performance of RS regenerating erasure codes is improved greatly than the similar erasure codes,and the total recovery time of the system is reduced by 20.8%~28.2% using hybrid recovery algorithm in the case of single fault.     

Novel construction of quasi-cyclic low-density parity-check codes with variable code rates for cloud data storage systems

This paper proposed a novel method for constructing quasi-cyclic low-density parity-check (QC-LDPC) codes of medium to high code rates that can be applied in cloud data storage systems, requiring better error correction capabilities. The novelty of this method lies in the construction of sparse base matrices, using a girth greater than 4 that can then be expanded with a lift factor to produce high code rate QC-LDPC codes. Investigations revealed that the proposed large-sized QC-LDPC codes with high code rates displayed low encoding complexities and provided a low bit error rate (BER) of 10⁻¹⁰ at 3.5 dB E_b/N₀ than conventional LDPC codes, which showed a BER of 10⁻⁷ at 3 dB E_b/N₀. Subsequently, implementation of the proposed QC-LDPC code in a software-defined radio, using the NI USRP 2920 hardware platform, was conducted. As a result, a BER of 10⁻⁶ at 4.2 dB E_b/N₀ was achieved. Then, the performance of the proposed codes based on their encoding–decoding speeds and storage overhead was investigated when applied to a cloud data storage (GCP). Our results revealed that the proposed codes required much less time for encoding and decoding (of data files having a 10 MB size) and produced less storage overhead than the conventional LDPC and Reed–Solomon codes.     

高性能时不变LDPC卷积码构造算法研究

该文基于由QC-LDPC码获得时不变LDPC卷积码的环同构方法,设计了用有限域上元素直接获得时不变LDPC卷积码多项式矩阵的新算法。以MDS卷积码为例,给出了一个具体的构造过程。所提构造算法可确保所获得的时不变LDPC卷积码具有快速编码特性、最大可达编码记忆以及设计码率。基于滑动窗口的BP译码算法在AWGN信道上的仿真结果表明,该码具有较低的误码平台和较好的纠错性能。     

系统RA码的基于WBF策略的改进BP译码算法

 针对重复累积(RA)码译码算法(BP算法和最小和算法)复杂度高或纠错性能下降的问题,将加权位翻转WBF的思想用于改进BP算法,提出了基于WBF策略的改进BP译码算法. 在每次迭代译码中若未能译出合法码字,则按一定规则进行位翻转操作,以期获得合法码字. 仿真结果表明,本算法能有效降低系统RA码的运算复杂度,且能保持优异的译码性能.     

HVD: horizontal-vertical-diagonal error detecting and correcting code to protect against with soft errors

This paper presents a high level error detection and correction method called HVD code to tolerate multiple bit upsets (MBUs) occurred in memory cells. The proposed method uses parity codes in four directions in a data part to assure the reliability of memories. The proposed method is very powerful in error detection while its error correction coverage is also acceptable considering its low computing latency. HVD code is useful for applications whose high error detection coverage is very important such as memory systems. Of course, this code can be used in combination with other protection codes which have high correction coverage and low detection coverage. The proposed method is evaluated using more than one billion multiple fault injection experiments. Multiple bit flips were randomly injected in different segments of a memory system and the fault detection and correction coverages are calculated. Results show that 100% of the injected faults can be detected. We proved that, this method can correct up to three bit upsets. Some hardware implementation issues are investigated to show tradeoffs between different implementation parameters of HVD method.     

Dual-CRC polar codes and dual-SCFlip decoding algorithm for cell search in 5G system

Polar codes become the coding scheme for control channels of enhanced mobile broadband (eMBB) scenarios in the fifth generation (5G) communication system due to their excellent decoding performance. For the cell search procedure in 5G system, some common information bits ( CIBs) are transmitted in consecutive synchronization signal blocks ( SSBs). In this paper, a dual-cyclic redundancy check ( dual-CRC) aided encoding scheme is proposed, and the corresponding dual-successive cancellation flip ( dual-SCFlip) algorithm is given to further improve the performance of polar codes in the low signal-to-noise ratio ( SNR) environment. In dual-CRC aided encoding structure, the information bits of polar codes in different transmission blocks add cyclic redundancy check (CRC) sequences respectively according to CIBs and different information bits (DIBs). The structure enlarges the size of CIBs to improve the block error ratio ( BLER) performance of the system. The dual-SCFlip decoder can perform bit flip immediately once CIBs is decoded completely, and then decode DIBs or terminate decoding in advance according to the CRC result, which reduces the delay of decoding and mitigates the error propagation effect. Simulation results show that the dual-CRC aided encoding scheme and dual-SCFlip decoder have significant performance improvement compared to other existing schemes with low SNR.     

Low Complexity Decoder Architecture for Low-Density Parity-Check Codes

In this paper, we propose a low complexity decoder architecture for low-density parity-check (LDPC) codes using a variable quantization scheme as well as an efficient highly-parallel decoding scheme. In the sum-product algorithm for decoding LDPC codes, the finite precision implementations have an important tradeoff between decoding performance and hardware complexity caused by two dominant area-consuming factors: one is the memory for updated messages storage and the other is the look-up table (LUT) for implementation of the nonlinear function Ψ(x). The proposed variable quantization schemes offer a large reduction in the hardware complexities for LUT and memory. Also, an efficient highly-parallel decoder architecture for quasi-cyclic (QC) LDPC codes can be implemented with the reduced hardware complexity by using the partially block overlapped decoding scheme and the minimized power consumption by reducing the total number of memory accesses for updated messages. For (3, 6) QC LDPC codes, our proposed schemes in implementing the highly-parallel decoder architecture offer a great reduction of implementation area by 33% for memory area and approximately by 28% for the check node unit and variable node unit computation units without significant performance degradation. Also, the memory accesses are reduced by 20%.     

Some Results on Convolutional Coupled Codes: Distance Properties, Performance, and Design

The class of Convolutional Coupled Codes is a promising alternative to classical Turbo-Codes. A Convolutional Coupled Code consists of a cascade of ν identical recursive systematic convolutional (RSC) outer codes and k inner block codes with parameters (2ν, ν, d_i). The codes are linked together such that only the systematic part of the outer codes is encoded with the inner block encoders. Only the redundancy from the inner and outer codes are transmitted. An estimation of the minimum distance is derived. The influence of number, code memory and code polynomials of the outer RSC codes on the distance properties and the convergence behavior of the iterative decoding scheme is studied. With respect to this results, we present a guideline for the optimal design of the RSC outer codes.     

Design of parallel fault-secure encoders for systematic cyclic block transmission codes

In this paper, we consider the problem of designing parallel fault-secure encoders for various systematic cyclic linear codes used in data transmission. It is assumed that the data to be encoded before transmission are stored in a fault-tolerant RAM memory system protected against errors using a cyclic linear error detecting and/or correcting code. The main idea relies on taking advantage of the RAM check bits to control the correct operation of the cyclic code encoder as well. A slightly modified encoder allows not only for encoding the transmission data stream but also, independently and in parallel, to generate the reference check bits which allow for concurrent error detection in the encoder itself. The error detection capacity proves to be effective and grants good levels of protection as shown by error injection campaigns on encoders for various standard linear cyclic error detecting and error correcting codes. Moreover, the complexity evaluation of the FPGA implementations of the encoders shows that their fault-secure versions compare favorably against the unprotected ones, both with respect to hardware complexity and the maximal frequency of operation.     

A Low Complexity Decoding Algorithm for Extended Turbo Product Codes

In this letter, we propose a low complexity algorithm for extended turbo product codes by considering both the encoding and decoding aspects. For the encoding part, a new encoding scheme is presented for which the operations of looking up and fetching error patterns are no longer necessary, and thus the lookup table can be omitted. For the decoder, a new algorithm is proposed to extract the extrinsic information and reduce the redundancy. This new algorithm can reduce decoding complexity greatly and enhance the performance of the decoder. Simulation results are presented to show the effectiveness of the proposed scheme.     

一种低译码复杂度的Turbo架构LDPC码

针对低密度奇偶校验(LDPC)码较大的译码复杂度和RAM占用,该文提出了一种低译码复杂度的Turbo架构LDPC码并行交织级联Gallager码 (Parallel Interleaved Concatenated Gallager Code,PICGC)。该文给出了PICGC的设计方法和编译码算法,并分析比较了PICGC译码器与LDPC译码器所需的RAM存储量,推导出RAM节省比的上界。理论分析和仿真结果表明,PICGC以纠错性能略微降低为代价,有效地降低译码复杂度和RAM存储量,且译码时延并未增加,是一种有效且易于实现的信道编码方案。