Search

A novel method for constructing the Latin square Low Density Lattice Codes (LDLC) parity check matrix is proposed in this paper. Based on the permutation matrix, a 6-cycle matrix is build firstly. Then the elements involved in the 6-cycle are detected and swapped, which is on the basis of the theory of adjacency matrix. Therefore, we obtain a check matrix, which is 6-cycle free and the nonzero elements obeying random distribution. Simulation results demonstrate that the proposed method has a lower symbol error rate (SER) compared with the previous works.

Correlated secret randomness is an essential resource for information-theoretic cryptography. In the context of secure two-party computation, the high level of efficiency achieved by information-theoretic protocols has motivated a paradigm of starting with correlated randomness, specifically random oblivious transfer (OT) correlations. This correlated randomness can be generated and stored during an offline preprocessing phase, long before the inputs are known. But what if some information about the correlated randomness is leaked to an adversary or to the other party? Can we still recover “fresh” correlated randomness after such leakage has occurred?

Decision diagrams are an efficient way of representing switching functions and they are easily mapped to technology. A layout of a circuit is directly determined by the shape and the complexity of the decision diagram. By combining the theory of error-correcting codes with decision diagrams, it is possible to form robust circuit layouts, which can detect and correct errors. The method of constructing robust decision diagrams is analogous to the decoding process of linear codes, and is based on simple matrix and look-up operations. In this paper, the performance of robust binary decision diagrams is analyzed by determining the error probabilities for such constructions. Depending on the error-correcting properties of the code used in the construction, the error probability of a circuit can be significantly decreased by a robust decision diagram.

In this paper, we propose a high-speed LDPC encoder architecture for the DVB-S2 standard. The proposed LDPC encoding architecture is based on parallel 360 bit-wise operations. The key issues for realizing a high speed are two kinds of index addresses and making efficient use of memory. We implemented a half-rate LDPC encoder on an FPGA, and confirmed that its maximum throughput is up to 10 Gbps with a 100 MHz clock.

In this paper we give several new constructions of WOM codes. The novelty in our constructions is the use of the so called Wozencraft ensemble of linear codes. Specifically, we obtain the following results. We give an explicit construction of a two-write Write-Once-Memory (WOM for short) code that approaches capacity, over the binary alphabet. More formally, for every e>0, 0

We consider the problem of efficient decoding of a random linear code over a finite field. In particular we are interested in the case where the code is random, relatively sparse, and use the binary finite field as an example. The goal is to decode the data using fewer operations to potentially achieve a high coding throughput, and reduce energy consumption. We use an on-the-fly version of the Gauss-Jordan algorithm as a baseline, and provide several simple improvements to reduce the number of operations needed to perform decoding. Our tests show that the improvements can reduce the number of operations used during decoding with 10-20% on average depending on the code parameters.

In this paper, we propose decision feedback equalizer based on LDPC (Low Density Parity Check) code for fast processing and performance improvement. LDPC code has good error correcting ability and performance approaching Shannon capacity. However, it has more long parity check matrix and the number of iteration. In proposed system, MSE (mean square error) of signal between decision device and decoder is fed back to equalizer. If we use this method, proposed system can improve performance because it corrects estimated channel response more accurately. In addition, proposed system can reduce complexity because it has a lower number of iterations than system that does not include feedback at same performance. We evaluate performance of OFDM system considered CFO and phase noise in multipath channel via simulation.

A constant weight codeword is a binary n-tuple with exactly r 1's. We show two circuits that generate constant weight codewords. The first is based on the combinatorial number system. Its input is an index to the codeword. That is, there are (n r) n-bit codewords with exactly r 1's. The index generates a unique codeword, and is a binary number between 0 and (n r) -1. Such a circuit is useful for encoding data. If a random constant weight codeword is needed, as in Monte Carlo simulations, then the index is random. If a random constant weight codeword only is needed, then our other circuit is even more compact. It is based on a trellis configuration. Both designs can be pipelined to produce one constant weight codeword per clock period. We give experimental results showing the efficiency of our designs on the SRC-6 reconfigurable computer.

Low complexity decoding algorithm is proposed to reduce the complexity of decoding algorithm for nonbinary quasi-cyclic LDPC codes. The algorithm uses methods of logarithm domain and look-up table based on the FFT-QSPA algorithm, avoiding multiplication and division calculations. These calculations make the hardware compute slowly. As a result, the algorithm makes the hardware easier to realize. The parity check matrices with quasi-cyclic form are constructed based on the finite fields, which are benefit for linear encoding based on the feedback shift registers. The letter presents a scheme combined with the constitution, coding and decoding of nonbinary quasi-cyclic LDPC codes with low complexity. The simulation shows that nonbinary quasi-cyclic LDPC codes achieve significant coding gains over RS codes with lower complexity and better performance.

The McEliece public-key cryptosystem is based on the fact that decoding unknown linear binary codes is an NP-complete problem. The interest on implementing post-quantum cryptographic algorithms, e.g. McEliece, on microprocessor-based platforms has been extremely raised due to the increasing storage space of these platforms. Therefore, their vulnerability and robustness against physical attacks, e.g., state-of-the-art power analysis attacks, must be investigated. In this work, we address mainly two power analysis attacks on various implementations of McEliece on an 8-bit AVR microprocessor. To the best of our knowledge, this is the first time that such side-channel attacks are practically evaluated.

Reed-Solomon (204,188) code has been widely used in many digital multimedia broadcasting systems. This paper focuses on the low complexity derivation of adaptive belief propagation bit-level soft decision decoding for this code. Simulation results demonstrate that proposed normalized min-sum algorithm as belief propagation (BP) process provides the same decoding performance in terms of packet-error-rate as sum-product algorithm. An outer adaptation scheme by moving adaptation process of parity check matrix out of the BP iteration loop is also introduced to reduce decoding complexity. Simulation results show that the proposed two schemes perform a good trade-off between the decoding performance and decoding complexity.

A new encoding technique for low density parity check (LDPC) code at the uplink of 3rd Generation Partnership Project Long Term Evolution (3GPP LTE) is proposed. The concept of approximate lower triangulation (ALT) is used where the parity check matrix is preprocessed and encoded in O (n ) complexity. This encoding technique is applied in the uplink of LTE system where single carrier frequency division multiple access (SC-FDMA) is used as the multiple access scheme. As the encoding is performed in a O (n ) complexity, it will outperform the existing LDPC encoding which is not used in LTE uplink due to its high encoding complexity. The proposed encoding is simulated in the SCFDMA scenario and the BER curve is shown.

In this work, we consider the pairwise error probability (PEP) of a linear programming (LP) decoder for a general binary linear code as formulated by Feldman et al. (IEEE Trans. Inf. Theory, March 2005) on a quantized additive white Gaussian noise (AWGN) channel. With a quantized AWGN (QAWGN) channel, we mean a channel where we first compute log-likelihood ratios as for an AWGN channel and then quantize them. Let H be a parity-check matrix of a binary linear code and consider LP decoding based on H. The output of the LP decoder is always a pseudo-codeword , of some pseudo-weight , where the definition of pseudo-weight is specific to the underlying channel model. In this work, we give a definition of pseudo-weight for a QAWGN channel based on an asymptotic (high signal-to-noise ratio) analysis of the PEP. Note that with maximum-likelihood decoding, the parameters of the quantization scheme, i.e., the quantization levels and the corresponding quantization region thresholds, that minimize the PEP of wrongly decoding to a non-zero codeword c when the all-zero codeword is transmitted is independent of the specific codeword c. However, this is not the case with LP decoding based on a parity-check matrix H, which means that the quantization scheme needs to be optimized for the given H. As a case study, we consider the well-known (3,5)-regular (155,64,20) Tanner code and estimate its minimum QAWGN pseudo-weight with 3 and 5 levels of quantization, in which the quantization scheme is optimized to maximize the minimum QAWGN pseudo-weight.

Courtois, Finiasz and Sendrier proposed in 2001 a practical code-based signature scheme. We give a rigorous security analysis of a modified version of this scheme in the random oracle model. Our reduction involves two problems of coding theory widely considered as difficult, the Goppa Parametrized Bounded Decoding and the Goppa Code Distinguishing.

This paper proposes a joint coding with three functions: source coding, channel coding, and public-key encryption. A codeword is simply generated as a product of an encoding matrix and a sparse information word. This encoding method has much lower encoding complexity than the conventional coding techniques in which source coding, encryption, and channel coding are successively applied to an information word. The encoding matrix is generated by using two linear error control codes and randomly generated nonsingular matrices. Encryption is based on the intractableness of factorizing a matrix into randomly constructed factor matrices, and of decoding an error control code defined by a random parity-check matrix. Evaluation shows that the proposed joint coding gives a lower bit error rate and a superior compression ratio than the conventional codings.

Irregular LDPC (Low Density Parity Check) code is a powerful error correction code in wireless communication applications. However, irregular LDPC decoder has limited instruction-level parallelism. This paper exploits the thread-level parallelism of irregular LDPC decoders with simultaneous multithreading (SMT) techniques. The simulations with random constructed parity check matrixes under different signal-to-noise ratios and three block lengths show that it can attain 16.7%-45.3% performance improvement by SMT technique with the area cost increasing by about 17.73%, which supposes that SMT is an efficient technique to improve the performance of irregular LDPC decoders.

We describe a protocol for quantum oblivious transfer, utilizing faint pulses of polarized light, by which one of two mutually distrustful parties ("Alice") transmits two one-bit messages in such a way that the other party ("Bob") can choose which message he gets but cannot obtain information about both messages (he will learn his chosen bit's value with exponentially small error probability and may gain at most exponentially little information about the value of the other bit), and Alice will be entirely ignorant of which bit he received. Neither party can cheat (ie deviate from the protocol while appearing to follow it) in such a way as to obtain more information than what is given by the description of the protocol. Our protocol is easy to modify in order to implement the All-or-Nothing Disclosure of one out of two string messages, and it can be used to implement bit commitment and oblivious circuit evaluation without complexity-theoretic assumptions, in a way that remains secure even against cheaters that have unlimited computing power. Moreover, this protocol is practical in that it can be realized with available opto-electronic apparatus while being immune to any technologically feasible attack for the foreseeable future.

On Crypto '88, Matsumoto, Kato, and Imai presented protocols to speed up secret computations with insecure auxiliary devices. The two most important protocols enable a smart card to compute the secret RSA operation faster with the help of a server that is not necessarily trusted by the card holder. It was stated that if RSA is secure, the protocols could only be broken by exhaustive scarch in certain spacts. Our main attacks show that much smaller search spaces suffice. These attacks are passive and therefore undetectable. It was already known that one of the protocols is vulnerable to active attacks. We show that this holds for the other protocol, too. More importantly, we show that our attack may still work if the smart card checks the correctness of the result; this was previously believed to be can easy measure excluding all active attacks. Finally, we discuss attach on related protocols.

In this paper, we discuss collusion-secure traceability codes for digital fingerprinting which is a technique for copyright protection of digital contents. We first state a generalization of conventional collusion attacks where illicit users of a digital content collude to create an illegal digital content. Then we propose a collusion-secure traceability code which can detect at least one colluder against it. We show the rate and properties of the proposed traceability code.

The use of syndrome coding in steganographic schemes tends to reduce distortion during embedding. The more complete model comes from the wet papers [FGLS05] which allow to lock positions that cannot be modified. Recently, BCH codes have been investigated, and seem to be good candidates in this context [SW06]. Here, we show that Reed-Solomon codes are twice better with respect to the number of locked positions and that, in fact, they are optimal. We propose two methods for managing these codes in this context: the first one is based on a naive decoding process through Lagrange interpolation; the second one, more efficient, is based on list decoding techniques and provides an adaptive trade-off between the number of locked positions and the embedding efficiency.

This paper deals with strategies to dramatically reduce the complexity for embedding based on syndrome coding. In contrast to existing approaches, our goal is to keep the embedding efficiency constant, i.e., to embed less complexly without increasing the average number of embedding changes, compared to the classic Matrix Embedding scenario. Generally, our considerations are based on structured codes, especially on BCH Codes. However, they are not limited to this class of codes. We propose different approaches to reduce embedding complexity concentrating on both syndrome coding based on a parity check matrix and syndrome coding based on the generator polynomial.

We show herein that a pattern based on FGLM techniques can be used for computing Grobner bases, or related structures, associated to linear codes. This Grobner bases setting turns out to be strongly related to the combinatorics of the codes.

The effectiveness of cancer treatment depends strongly on an accurate diagnosis. In this paper we propose a system for automatic and precise diagnosis of a tumor's origin based on genetic data. This system is based on a combination of coding theory techniques and machine learning algorithms. In particular, tumor classification is described as a multiclass learning setup, where gene expression values serve the system to distinguish between types of tumors. Since multiclass learning is intrinsically complex, the data is divided into several biclass problems whose results are combined with an error correcting linear block code. The robustness of the prediction is increased as errors of the base binary classifiers are corrected by the linear code. Promising results have been achieved with a best case precision of 72% when the system was tested on real data from cancer patients.

Wet paper codes were proposed as a tool for constructing steganographic schemes with an arbitrary selection channel that is not shared between the sender and the recipient. In this paper, we describe new approaches to wet paper codes that enjoy low computational complexity and improved embedding efficiency (number of message bits per embedding change). Some applications of wet paper codes to steganography and data embedding in binary images are discussed.

A bandwidth efficient communication model is propoded via a narrowband band-pass filter at the transmitting end of the system. In order to reduce the ISI caused by the filter, a joint detection algorithm based on low-density parity check matrix codes (LDPC) is presented.

In this paper, we describe a kind of high rate low density parity check (LDPC) code and its decoding scheme for ultra wideband (UWB) communication. Particularly, the proposed scheme uses a hybrid soft normalization algorithm from the autocorrelations of UWB signals to initialize the LDPC decoder, and it integrates several normalized soft values of UWB signals as sine (BPSK) or cosine (PPM) elements by using the window concept.

We present a wide experimental work evaluating the behaviour of Recursive ECOC (RECOC) [1] learning machines based on Low Density Parity Check (LDPC) coding structures. We show that owing to the iterative decoding algorithms behind LDPC codes, RECOC multiclass learning is progressively achieved. This learning behaviour confirms the existence of new boosting dimension, the one provided by the coding space. We present a method for searching potential good RECOC codes from LDPC ones. Starting from a properly selected LDPC code, we assess the effect of boosting in both weak and strong binary learners. For nearly all domains, we find that boosting a strong learner like a Decision Tree is as effective as boosting a weak one like a Decision Stump. This surprising result substantiates the hypothesis that weakening strong classifiers by boosting has a decorrelation effect, which can be used to improve RECOC learning.

With many multimedia delivery schemes a client does not necessarily receive a given media content entirely (e.g. router congestions can lead some information to be lost). Mechanisms like error concealment and error resilient video coding allow the receiver to deal with partially received data and to play the content, with decreased quality though. Packet-level Forward Error Correction (FEC) can be used as a complementary technique to counter the effects of losses and reconstruct the missing packets. However if the number of packets received is too low for the FEC decoding process to finish, the received parity packets may turn out to be useless, and finally more source packets may be unavailable to the application than if FEC had not been used at all. This paper analyzes the adequacy of the LDGM Staircase, LDGM Triangle and RSE FEC codes to offer a partial reliability service for media content distribution over any kind of packet erasure channel, that is to say a service that enables a receiver to reconstruct parts of the content even if the FEC decoding process has not finished. We analyze this service in the context of a broadcasting system having no feedback channel and that offers media content distribution, like Digital Video/Audio Broadcasting.

In the previous chapters, we have already seen constructions of asymptotically good codes of good rate over both large alphabets (the AG-codes from Chapter 6) and the binary alphabet (the concatenated codes from Chapter 8), that are efficiently list decodable up to a “maximum” possible radius.

In this chapter, we review the basic definitions relating to error-correcting codes and standardize some notation. We then give a brief description of the fundamental code families and constructions that will be dealt with and used in this book. Finally, we discuss the structure of this work and the main results which are established in the technical chapters that follow, explaining in greater detail how the results of the various chapters fit together.

For fixed positive integers k, q, r with q a prime power and large m, we investigate matrices with m rows and a maximum number Nq(m, k, r) of columns, such that each column contains at most r nonzero entries from the finite field GF(q) and each k columns are linearly independent over GF(q). For even k we prove the lower bounds Nq(m, k, r) = Ω(mkr/(2(k-1))), and Nq(m, k, r) = Ω(m(k-1)r/(2(k-2))) for odd k ≥ 3. For k = 2i and gcd(k-1, r) = k-1 we obtain Nq(m, k, r) = Θ(mkr/(2(k-1))), while for any even k ≥ 4 and gcd(k - 1, r) = 1 we have Nq(m, k, r) = Ω(mkr/(2(k-1)) ċ (log m)1/(k-1)). For char (GF(q)) > 2 we prove that Nq(m, 4, r) = Θ(m⌈4r/3⌉/2), while for q = 2l we only have Nq(m, 4, r) = O(m⌈4r/3⌉/2). We can find matrices, fulfilling these lower bounds, in polynomial time. Our results extend and complement earlier results from [4,14], where the case q = 2 was considered.

We investigate the use of vector bundles over finite fields to obtain a geometric view of decoding algebraic-geometric codes. Building on ideas of Trygve Johnsen, who revealed a connection between the errors in a received word and certain vector bundles on the underlying curve, we give explicit constructions of the relevant geometric objects and efficient algorithms for some general computations needed in the constructions. The use of vector bundles to understand decoding as a geometric process is the first application of these objects to coding theory.

In a systematic erasure code for the correction of two simultaneous erasures, each information symbol must have two associated parity symbols. When implemented in a redundant array of independent disks (RAID), performance requirements on the update penalty necessitate that each information symbol be associated with no more parity symbols than the two required. This leads to a simple graph model of the erasure codes, with parity symbols as vertices and information symbols as edges. Ordering the edges so that no more than f check disks (vertices) appear among any set of d consecutive edges is found to optimize access performance of the disk array when d is maximized. These cluttered orderings are examined for the complete graph Kn. The maximum number d of edges is determined precisely when f ≤ 5 and when f = n - 1, and bounds are derived in the remaining cases.

We consider the design of phase shift keyed space-time coded modulation for two antenna systems based on linear codes over rings. Design rules for constructing full diversity systematic space-time codes based on underlying existing algebraic codes were first presented by Hammons and El Gamal in 2000. We reformulate and simplify these design rules, resulting in the condition that the characteristic polynomial of the parity generation matrix must be irreducible. We further extend the results to non-systematic codes. These results yield a recursive construction based on the Schur determinant formula. The resulting block codes are guranteed to provide full diversity advantage. In addition, the code construction is such that the corresponding parity check matrix is sparse, enabling the use of the powerful Sum-Product algorithm for decoding.

A general framework for the design of error adaptive learning algorithms in multiple output domains based on Dietterich's ECOC approach, recursive error output correcting codes and iterative APP decoding methods is proposed. A particular class of these Recursive ECOC (RECOC) learning algorithms based on Low Density Parity Check is presented.

Steiner triple systems are well studied combinatorial designs that have been shown to possess properties desirable for the construction of multiple erasure codes in RAID architectures. The ordering of the columns in the parity check matrices of these codes affects system performance. Combinatorial problems involved in the generation of good and bad column orderings are defined, and examined for small numbers of accesses to consecutive data blocks in the disk array.

Rao and Nam [7] proposed a secret-key cryptosystem based on error correcting codes. After breaking the original system by a chosenplaintext attack, Struik and van Tilburg [8] improved the Rao-Nam cryptosystem. However, the size of the key remains a practical problem also for their improved scheme. We discuss several modifications of the improved Rao-Nam system. The goal of these modifications is to reduce the amount of secret key that needs to be exchanged, while maintaining the security of the system.1

The paper addresses the problem of bad signature identification in batch verification of digital signatures. The number of generic tests necessary to identify all bad signatures in a batch instance, is used to measure the efficiency of verifiers. The divide-and-conquer verifier DCV α (x,n) is defined. The verifier identifies all bad signatures in a batch instance x of the length n by repeatedly splitting the input into α sub-instances. Its properties are investigated. In particular, probability distributions for the number of generic tests necessary to identify one, two and three bad signatures, are derived. The average numbers of GT tests necessary to identify bad signatures ranging from 1 to 16 are obtained from computer simulation. Further, a Hamming verifier (HV) is defined which allows to identify a single bad signature in a batch of the length n=2 k -1 using k+2 tests. HV is generalised into the two-layer Hamming verifier (2HV). Given a batch instance of the length 2 k − 2, the 2HV verifier identifies a single bad signature using k+2 tests and two bad signatures in expense of 3k+3 tests. The work is concluded by comments about a general model for verification codes identifying t bad signatures and the design of verifiers using combinatorial structures.

We present a soft-decision decoding method for Reed-Solomon codes (RS codes) using both cyclic and squaring permutations. These permutations are used to provide a convenient sequence which is predicted to have relatively low complex error pattern with respect to a modified Fano sequential algorithm[1]. In order to preserve bit-level soft-decision values, each sequence of those permutation groups must keep equal weight distribution in symbol and bit level. Trellis construction is based on Wolf's method[2] and a binary systematic parity check matrix of RS codes is used for bit-level decoding[9]. In simulation results, it is shown that a hybrid of those two permutations can be used for low complexity decoding approaching maximum likelihood performance.

From the previous chapter one might get the impression that the theory of error-correcting codes is equivalent to the theory of finite geometry or arrangements over finite fields. This is not true from a practical point of view. A code is useless without a decoding algorithm. For engineers the total performance of the encoding and decoding scheme is important.

Hwang and Chen have proposed a private-key cryptosystem that provides joint error correction, encryption, and “message” integrity. The scheme is based on algebraic error-correcting codes, using random chaining technique. It was shown that obtaining a combinatorially equivalent code, under ciphertext-only attack, requires O(k2n) operations and O(k2n/2) ciphertexts, where n and k are the length and dimension of the code respectively. It was further claimed that obtaining an equivalent code is not sufficient to “totally” break the system. In this paper, a chosen-plaintext attack is presented that is able to break the system, requiring O[(n - k)2k/2] ciphertexts and O[(n - k)2 k] operations; the attack is based on obtaining a combinatorially equivalent code. Finally, a modified version of the scheme is proposed that overcomes the weaknesses of the original Hwang-Chen scheme; the complexity to break this modified scheme is O(k2n/2) ciphertexts and O(kn2n/2) operations.

An algorithm for decoding of linear binary block codes based on the iterative probabilistic error-correction is considered theoretically and experimentally. Assuming the sparse code parity-check matrix it is demonstrated that, with probability close to one, the algorithm works far beyond the half minimum distance with complexity linearly proportional to the codeword length and the average number of per bit employed parity-checks.

We present an algorithm that achieves general syndrome decoding of a (n, k, r) linear rank distance code over GF(q m ) in O(nr + m)3q(m−r)(r−1)) elementary operations. As a consequence, the cryptographical schemes [Che94, Che96] which rely on this problem are not secure with the proposed parameters. We also derive from our algorithm a bound on the minimal rank distance of a linear code which shows that the parameters from [Che94] are inconsistent.

Several declustering functions for distributing multi-attribute data on a set of disks have been proposed in recent years. Since these functions map grid regions to disks in a static way, performance deteriorates in case of dynamic datasets and/or non-stationary data distributions. We first analyze how declustering functions can be extended in order to deal with dynamic datasets without requiring periodic reorganizations. In order to support dynamic declustering, we propose to organize the directory as a parallel Multilevel Grid File. On this structure we experiment five dynamic declustering functions and two index-based allocation methods that only use locally available information. This first comparison among the two approaches reveals that methods based on local criteria always yield better results.

We consider the extremal problem to determine the maximal number N(m, k, r) of columns of a 0–1 matrix with m rows and at most r ones in each column such that each k columns are linearly independent modulo 2. For fixed integers k ≥ 2 and r ≥ 1, we show the probabilistic lower bound N(m, k, r) = Ω(mkr/2(k−1)); for k a power of 2, we prove the upper bound N(m, k, r) = O(n[kr/(k−1)]/2), which matches the lower bound for infinitely many values of r. We give some explicit constructions.

We show a simple and efficient construction of a pseudo-random generator based on the intractability of an NP-complete problem from the area of error-correcting codes. The generalor is proved as secure as a hard instance of the syndrome decoding problem. Each application of the scheme generates a linear amount of bits in only quadratic computing time.

A certain number of public-key cryptosystems based on error-correcting codes have been proposed as an alternative to algorithms based on number theory. In this paper, we analyze algorithms that can be used to attack such cryptosystems in a very precise way, and optimize them. Thus, we obtain some more efficient attacks than those previously known. Even if they remain unfeasible, they indicate the cryptosystems parameters forbidden by the existence of these algorithms.