This paper presents three types of post-quantum encrypted vector computations over the prime field. Based on the linearity and quasi-cyclicity of non-binary QC-MDPC code, the method can perform vector addition (VA), scalar multiplication (SM), and cyclic shift (CS) without decrypting ciphertexts, where the scalar value and shift width are public plaintext data. Com-binations of these computations enable some important practical computations, e.g., the batch of weighted sums and convolution of vector elements. The parity-check matrix of QC-MDPC code used in the key encapsulation is modified to remove the systematic information part of the ciphertext. The decoding failure rate is evaluated by simulation for QC-MDPC code over$\mathbb{F}_{q}$with the non-binary sum-product algorithm and the parallel symbol flipping decoding. Also the work factors of the information set decoding for key recovery and decoding attacks are calculated. The numerical results show that, using a (9602, 4801) code over$\mathbb{F}_{251}$, the method can perform up to three VAs and arbitrary numbers of SMs and CSs.

This paper presents a modified bit-flipping (BF) decoding algorithm for moderate-density parity-check codes using a property of the number of unsatisfied parity checks (NUPCs) in uncorrected error positions. The proposed BF algorithm selects candidate flipping positions using the current NUPC, and then selects one flipping position based on a sum of NUPCs in suspicious positions after tentative flipping of each candidate position. The block error rate (BLER) is evaluated by computer simulation, and the results show that the presented BF algorithm gives lower BLERs compared to existing decoding algorithms.

In this paper, we work on the symbolwise maximum a posteriori probability (MAP) estimation of channel input symbol from m (≥ 2) received words (traces) having inser- tion/deletion/substitution (IDS) errors, where the errors are independent between m received words. This problem is motivated by readout process in next-generation sequencers of DNA storage. The MAP estimation is based on the belief propagation algorithm on a factor graph, which represents the joint probability of a channel input word and m pairs of channel output word and drift vector. We also propose a heuristic estimation algorithm for m ≥ 4 to reduce the computational complexity. Simulation results show the relation between channel IDS error rate and estimation error rate.

This paper presents a successive cancellation (SC) decoding of polar codes for insertion/deletion error channels in which received word may have multiple insertion and deletion errors simultaneously. This decoding is an extension of existing SC decoding for d-deletion channels, that is, the decoding of this paper expresses occurrences of insertions and deletions by a sequence of drift values, and the drift values are included in the recursive calculation of SC decoding. Simulation results show that the presented SC list decoding gives lower block error rates compared to existing IDS error correction coding based on LDPC code and synchronization marker.

This paper considers Slepian-Wolf (SW) coding in which side-information (SI) has insertion and deletion errors, presuming that the SI is given as a binary vector generated by temporal and/or spatial interpolation or extrapolation of related binary vectors. The coding could be regarded as a simplified model of SW coding in distributed video coding. From the generation process of SI vector, we define a hypothetical error model in the SI vector as an insertion/deletion/substitution error channel, and then show a coding scheme using nonbinary LDPC code. Decoding is based on an iterative multi-path decoding of forward-backward algorithm and FFT sum-product algorithm. Simulation results show the relations between insertion/deletion probability and decoded bit error rates.

Several types of insertion/deletion/substitution error correction codings have been proposed for channels with imperfect synchronization. Most of the conventional coding schemes assume insertion/deletion errors of bit granularity, while in some applications, e.g. bit patterned media recording, insertion/deletion errors occur as a result of accumulation of small synchronization errors. This paper considers a timing-drift channel model in which a fraction of bit (i.e., 1 /ν-bit) is inserted and deleted, and describes application of conventional marker-based IDS error correction coding to the channel. Also simulation results show bit error rates of the marker-based coding.

Data intensive computing often requires high-throughput data transfers between components, e.g., processors and memories. Low-latency lossless data compression will be effective to improve the throughput of data buses. This paper proposes a lossless data compression, X-Hash, using a combination of multiple-type dictionaries.

In this paper, we deal with coding for synchronization errors. In conventional studies, to combat such errors, periodic synchronization markers are inserted or specifier and watermark codes are concatenated. These codes enable estimation of synchronous errors, but do not have ability to correct random errors. Low-density parity-check codes are usually concatenate to correct random errors. Due to the lack of dependence of information, periodic synchronization marker insertion prevents codes to approach the capacity. Recently, it is observed that spatially-coupled codes universally approach the symmetric information rate (SIR) of arbitrary finite state Markov channels. We introduce a synchronously erroneous finite state Markov channel model whose SIR is computable. Numerical experiments demonstrate spatially-coupled codes approach the SIR of the channel.

This paper presents an adaptive erasure correction coding with lossless data compression to reduce the data read/write amount required to recover from single-and double-disk failures in disk arrays. The proposed method utilizes two types of redundancies to reduce the recovery cost, that is, data redundancy, meaning that data block may be compressed to a smaller size, and storage space redundancy, meaning that disk array may have unused storage space. To utilize these redundancies, the code rate of erasure correction coding is adaptively determined depending on the compressed data size and available storage space. Results of a simple simulation show that the proposed method can reduce the recovery cost without affecting the response time of failure-free operations. For a disk array of 6 disks with average compression ratio 0.6 and utilization ratio 0.7, the read data amount for single-failure recovery is reduced by a factor of 0.24.

The computational performance of recent processors is often restricted by the delay of off-chip memory accesses, and so low-delay data compression should be effective to improve the processor performance. This paper proposes differential base pattern coding suitable for high-speed parallel decoding. Evaluation shows that the compression ratio of the coding is comparable or superior to that of conventional codings.

Distributed video coding (DVC) is a compression method that aims to produce low complexity encoding. One of the main practical problems facing DVC is that the encoder must know the required rate. Theoretically, the rate is lower bounded by the conditional entropy of the source given the side information. In practice, there are losses that must also be taken into account in estimating the rate. However, an accurate rate estimate starts with an accurate estimate of the conditional entropy. In this paper we propose a computationally efficient method for accurately estimating the conditional entropy.

This paper proposes an adaptive selection method of synchronization marker to improve the error correction capability of insertion/deletion/substitution error correcting code. The adaptive markers are inserted into every d bits of a codeword of LDPC code, where the marker value is determined depending on the neighboring bits of the codeword. This paper also shows a forward-backward algorithm to calculate the symbol-by-symbol likelihood. Evaluation shows that the bit error rate of the proposed method is lower than that of the conventional method using fixed synchronization marker.

This paper examines the applicability of the genetic algorithm (GA) to generation of nonbinary low-density parity-check (LDPC) codes over GF(q) which is suitable for distributed video coding (DVC). Error probability distribution in side-information of the DVC is approximated by Gaussian and Laplace distributions, and then a fitness of an LDPC matrix is defined under this approximation. The GA is designed to avoid LDPC matrices having small girth in the Tanner graph and to obtain column vectors with appropriate Hamming weight. This paper also outlines a parallel computation system using a cluster of personal computers to implement the proposed GA with reasonable cost. Evaluation shows that the decoded symbol error rate (SER) of the generated LDPC code is lower than that of randomly constructed LDPC code with the minimum girth of six. For example, in a 256-ary channel of Gaussian error distribution with standard deviation δ = 3.00, the decoded SER of a rate-1/2 code generated by the GA is 3.0 × 10-4, while that of a randomly constructed code is 4.4 × 10-1.

Solid-state drive (SSD) has advantages over hard-disk drive (HDD) in terms of power consumption, random access time, and resilience to shock and vibration. Large capacity SSD usually requires high-density multi-level cell flash memory fabricated with deep-submicron process. High-density memory chips, however, are vulnerable to soft errors caused by, for example, fluctuations of gate voltage and charge level in the floating gate. This paper proposes a hierarchical three-level error control coding suitable for the dependable SSD. The proposed coding is capable of correcting multiple random bit errors, as well as of recovering from single chip failures. Evaluation shows that the proposed coding scheme provides strong error correction capability. For example, bit error rate (BER) of the SSD is reduced from 1.08 × 10-4to 2.44 × 10-19by using the proposed coding, that is, using two BCH codes with different error correction capabilities for the first and the second levels, and the simple parity-check code for the third level. Extra one spare memory chip in the SSD improves mean time to data loss (MTTDL) from 13 years to 34 years.

M-Spotty byte error control codes are very effective for correcting/detecting errors in semiconductor memory systems using recent high-density RAM chips with wide I/O data, e.g., 8, 16, or 32 bits. In this case, width of the I/O data is called a byte. A spotty byte error is defined as random i-bit errors within a byte of length 6-bit, where t les b. Especially, M-spotty byte error is defined as multiple spotty byte errors in a byte. M-spotty byte error control code is characterized by m-spotty distance which includes Hamming distance as a special case for t = 1 or t = b. The MacWilliams identity provides the relation of weight distribution of a code and that of its dual code. This paper presents the MacWilliams identity for m-spotty weight enumerator of the m-spotty byte error control codes. Also, this clarifies that the indicated identity includes the MacWilliams identity for Hamming weight enumerator as a special case.

Nonbinary M-ary words processed by data entry systems often suffer from asymmetric errors. In character recognition systems, for example, two symbols a/sub i/ and a/sub j/ with similar shapes have a high probability of being mistaken for one another. Among the many types of data processed by data entry systems, M-ary words selected from a specified codebook, such as postal codes and product numbers, should be strongly protected from asymmetric errors because these words are often used for indexing a database. We propose a new class of nonsystematic M-ary asymmetric error correcting codes which can be utilized to generate these codebooks. In order to effectively correct asymmetric errors, the new class of codes is designed based on a multilevel coding method and a set partitioning algorithm. Evaluation shows that the proposed codes have a low decoded symbol error rate.

Nonbinary M-ary symbols such as alphanumeric characters are commonly used in data entry devices, e.g., keyboards and character recognition devices. The M-ary symbols processed by these devices are sometimes mistaken for other symbols due to errors such as mistyping in keyboards or misreading in character recognition systems. These errors are generally asymmetric, not symmetric. For example, the symbols corresponding to adjacent keys in a keyboard have a high error probability due to mistapping. Similarly, in character recognition systems, two symbols having similar shape have high error probability to be misrecognized. These asymmetric errors can be corrected or detected by using M-ary asymmetric symbol error control codes. We propose a new class of M-ary single asymmetric symbol error correcting codes by using a new class of rings obtained from a direct product of Galois fields. Asymmetric symbol errors are expressed by an error directionality graph, based on which the error correction capability of the codes is determined. The code is defined by a parity check matrix over the ring and functions which map a set of M-ary symbols into the ring. One of the functions is derived from the graph coloring problem of the error directionality graph. The proposed codes have greater information symbol length than the existing M-ary single symmetric symbol error correcting codes.