Search

The rate of a network code is the ratio of the block size of the network’s messages to that of its edge codewords. We compare the linear capacities and achievable rate regions of networks using finite field alphabets to the more general cases of arbitrary ring and module alphabets. For non-commutative rings, two-sided linearity is allowed. Specifically, we prove the following for directed acyclic networks. First, the linear rate region and the linear capacity of any network over a finite field depend only on the characteristic of the field. Furthermore, any two fields with different characteristics yield different linear capacities for at least one network. Second, whenever the characteristic of a given finite field divides the size of a given finite ring, each network’s linear rate region over the ring is contained in its linear rate region over the field. Thus, any network’s linear capacity over a field is at least its linear capacity over any other ring of the same size. An analogous result also holds for linear network codes over module alphabets. Third, whenever the characteristic of a given finite field does not divide the size of a given finite ring, there is some network whose linear capacity over the ring is strictly greater than its linear capacity over the field. Thus, for any finite field, there always exist rings over which some networks have higher linear capacities than over the field. [ABSTRACT FROM AUTHOR]

We consider the problem of constructing codes that can correct $\delta $ deletions occurring in an arbitrary binary string of length $n$ bits. Varshamov–Tenengolts (VT) codes, dating back to 1965, are zero-error single deletion $(\delta =1)$ correcting codes and have an asymptotically optimal redundancy. Finding similar codes for $\delta \geq 2$ deletions remains an open problem. In this paper, we relax the standard zero-error (i.e., worst-case) decoding requirement by assuming that the positions of the $\delta $ deletions (or insertions) are independent of the code word. Our contribution is a new family of explicit codes, that we call Guess & Check (GC) codes, that can correct with high probability up to a constant number of $\delta $ deletions (or insertions). GC codes are systematic; and have deterministic polynomial time encoding and decoding algorithms. We also describe the application of GC codes to file synchronization. [ABSTRACT FROM AUTHOR]

For nonnegative integers $n$ , $d$ , and $w$ , let $A(n,d,w)$ be the maximum size of a code $C \subseteq \mathbb {F}_{2}^{n}$ with a constant weight $w$ and minimum distance at least $d$. We consider two semidefinite programs based on quadruples of code words that yield several new upper bounds on $A(n,d,w)$. The new upper bounds imply that $A(22,8,10)=616$ and $A(22,8,11)=672$. Lower bounds on $A(22,8,10)$ and $A(22,8,11)$ are obtained from the $(n,d)=(22,7)$ shortened Golay code of size 2048. It can be concluded that the shortened Golay code is a union of constant-weight $w$ codes of sizes $A(22,8,w)$. [ABSTRACT FROM AUTHOR]

Abstract Locally recoverable codes are error-correcting codes allowing local recovery of lost encoded data in a codeword. We give a method to construct locally recoverable codes from rational maps between affine spaces, whose fibres are used as recovery sets. The recovery of erasures is carried out by Lagrangian interpolation in general and simply by one addition in some good cases. We first state the general construction of these codes and study its main properties. Next we apply it to several types of codes, including algebraic geometry codes, Reed–Muller, and other related codes. The existence of several recovering sets for the same coordinate and the possibility of recover more than one erasure at the same time are also treated. [ABSTRACT FROM AUTHOR]

Abstract In this paper, we study deep holes of Gabidulin codes in both rank and Hamming metrics. Specifically, first, we give a tight lower bound for the distance of any word to a Gabidulin code and a sufficient and necessary condition for achieving this lower bound as well. Then, a class of deep holes of a Gabidulin code are discovered. Furthermore, we obtain some other deep holes for certain Gabidulin codes. [ABSTRACT FROM AUTHOR]

Novel fault leveling techniques based on address remapping (AR) are proposed in this paper. We can change the logical-to-physical address mapping of the page buffer such that faulty cells within a flash page can be evenly distributed into different codewords. Therefore, the adopted ECC scheme can correct them effectively. Based on the production test or on-line BIST results, the fault bitmap can be used for executing the heuristic fault leveling analysis (FLA) algorithm and evaluating control words used to steer fault leveling. A new page buffer architecture suitable for address remapping is also proposed. According to experimental results, repair rate, yield, and reliability can be improved significantly with negligible hardware overhead. [ABSTRACT FROM AUTHOR]

This paper proposes a new scheme to secure the transmissions in an untrusted decode-and-forward (DF) relaying network. A legitimate source node, Alice, sends her data to a legitimate destination node, Bob, with the aid of an untrusted DF relay node, Charlie. To secure the transmissions from Charlie during relaying time slots, each data codeword is secured using a secret-key codeword that has been previously shared between Alice and Bob during the perfectly secured time slots (i.e., when the channel secrecy rate is positive). The secret-key bits exchanged between Alice and Bob are stored in a finite-length buffer and are used to secure data transmission whenever needed. We model the secret-key buffer as a queueing system and analyze its Markov chain. Our numerical results show the gains of our proposed scheme relative to benchmarks. Moreover, the proposed scheme achieves an upper bound on the secure throughput. [ABSTRACT FROM AUTHOR]

We study covering codes of permutations with the $\ell _\infty $ -metric. We provide a general code construction, which combines short building-block codes into a single long code. We focus on cyclic transitive groups as building blocks, determining their exact covering radius, and showing a linear-time algorithm for finding a covering codeword. When used in the general construction, we show that the resulting covering code asymptotically out-performs the best known code while maintaining linear-time decoding. We also bound the covering radius of relabeled cyclic transitive groups under conjugation, showing that the covering radius is quite robust. While relabeling cannot reduce the covering radius by much, the downside is that we prove the covering radius cannot be increased by more than 1 when using relabeling. [ABSTRACT FROM AUTHOR]

Upper bounds on the error probability of channel coding are derived for codebooks drawn from random codebook ensembles with various independence and symmetry assumptions. For regular decoding (without an erasure option), the random coding union bound of Polyanskiy et al. is improved by carefully taking ties (equal likelihood scores) into account. It is shown that the improved bound is always better than threshold-decoding based bounds. The framework is extended to the case of decoding with an erasure option, deriving several achievability bounds in the same spirit. In order to exemplify the merits of the approach, the bounds are evaluated for the case of pairwise-independent uniformly-distributed ensembles (e.g., shifted random linear codes). [ABSTRACT FROM AUTHOR]

A (t, n)-secret sharing scheme is a method of distribution of information among n participants such that t > 1 can reconstruct the secret but t > 1 cannot. There is numerous research about secret sharing schemes. However there is little research on secret sharing schemes based on extension fields. In this paper, we study secret sharing schemes based on extension fields over finite fields. We use two methods to recover the secret. We define the access structure and the accessibility degree for these secret sharing schemes. We also describe our theorems, definitions and a corollary. [ABSTRACT FROM AUTHOR]

The minimum energy, and, more generally, the minimum cost, to transmit one bit of information was recently derived for bursty communication when information is available infrequently at random times at the transmitter. Furthermore, it was shown that even if the receiver is constrained to sample only a fraction $\rho \in ~(0,1]$ of the channel outputs, there is no capacity penalty. That is, for any strictly positive sampling rate $\rho $ , the asynchronous capacity per unit cost is the same as under full sampling, i.e., when $\rho =1$ . Moreover, there is no penalty in terms of decoding delay. These results are asymptotic in nature, considering the limit as the number $B$ of bits to be transmitted tends to infinity, while the sampling rate $\rho $ remains fixed. A natural question is then whether the sampling rate $\rho (B)$ can drop to zero without introducing a capacity (or delay) penalty compared with full sampling. We answer this question affirmatively. The main result of this paper is an essentially tight characterization of the minimum sampling rate. We show that any sampling rate that grows at least as fast as $\omega (1/B)$ is achievable, while any sampling rate smaller than $o(1/B)$ yields unreliable communication. The key ingredient in our improved achievability result is a new, multi-phase adaptive sampling scheme for locating transient changes, which we believe may be of independent interest for certain change-point detection problems. [ABSTRACT FROM PUBLISHER]

Viterbi decoders are one of the most popular error-correcting channel decoders in wireless communication devices. However, a Viterbi decoder is also usually the dominant module in the mobile devices in terms of power consumption. To avoid the superfluous codeword decoding and reduce the power consumption, this paper proposes a low-power codeword-based Viterbi decoder and its corresponding VLSI architecture with the following advantages and contributions. Firstly, instead of the segment-based error detection (a segment is composed of $$K - 1$$ received codewords, and K is the constraint length), the proposed decoder can detect whether each received codeword is erroneous. The fine-grained error detection will result in fewer codewords that have to be corrected through the Viterbi decoder. Secondly, based on the codeword-based error detection, we develop a simple method to locate and correct the isolated faulty codewords that do not appear successively. As a result, the activation times of the Viterbi decoder can be further decreased. Furthermore, the survivor memory unit of the proposed codeword-based Viterbi decoder is split into several decoding stages and the corresponding stages can be disabled with a clock-gating technique when the codewords are non-erroneous. Experimental results show that the proposed decoder can save up to 30.85% power saving with negligible area and delay overheads compared with the previous segment-based design. [ABSTRACT FROM AUTHOR]

Polar codes have gained significant amount of attention during the past few years and have been selected as a coding scheme for the next generation of mobile broadband standard. Among decoding schemes, successive-cancellation list (SCL) decoding provides a reasonable tradeoff between the error-correction performance and hardware implementation complexity when used to decode polar codes, at the cost of limited throughput. The simplified SCL (SSCL) and its extension SSCL-SPC increase the speed of decoding by removing redundant calculations when encountering particular information and frozen bit patterns (rate one and single parity check codes), while keeping the error-correction performance unaltered. In this paper, we improve SSCL and SSCL-SPC by proving that the list size imposes a specific number of path splitting required to decode rate one and single parity check codes. Thus, the number of splitting can be limited while guaranteeing exactly the same error-correction performance as if the paths were forked at each bit estimation. We call the new decoding algorithms Fast-SSCL and Fast-SSCL-SPC. Moreover, we show that the number of path forks in a practical application can be tuned to achieve desirable speed, while keeping the error-correction performance almost unchanged. Hardware architectures implementing both algorithms are then described and implemented: It is shown that our design can achieve \mathbf 1.86 Gb/s throughput, higher than the best state-of-the-art decoders. [ABSTRACT FROM PUBLISHER]

We define a variable-length code having the property that no (non-empty) prefix of each its codeword is a suffix of any other one, and vice versa. This kind of code can be seen as an extension of two well-known codes in the literature, called, respectively, fix-free code and non-overlapping code. In this paper we present constructive algorithms for such codes and some numerical results about their cardinality. [ABSTRACT FROM PUBLISHER]

This paper provides a brief and insightful examination of the advantages achieved by employing combined phase offsetting and power allocation mechanisms in the space-time block coded (STBC) transmission of spatial modulation schemes with cyclic structure (CSM). In order to achieve increased coding gain distances (CGDs) between transmitted code words (CWs), the power allocation mechanism is cascaded to the constellation mapping process of a STBC-CSM scheme, and the optimal power and phase weights for the conveyed information symbols, together with the phases for each CW, are searched by a heuristic algorithm based on differential evolution that yields the best CGD available for the employed CWs. The outcomes of the optimization study, which is focused on maximizing the minimum CGD between all possible CW combinations for different numbers of antennas and modulation schemes, are then used to investigate and exhibit the average enhancements in the communications reliability. [ABSTRACT FROM AUTHOR]

We formulate a model for intermittent communication that can capture bursty transmissions or a sporadically available channel, where in either case the receiver does not know $a~priori$ when the transmissions will occur. Focusing on the point-to-point case, we develop a decoding structure, decoding from pattern detection, and its achievable rate for such communication scenarios. Decoding from pattern detection first detects the locations of code word symbols and then uses them to decode. We introduce the concept of partial divergence and study some of its properties in order to obtain stronger achievability results. As the system becomes more intermittent, the achievable rates decrease due to the additional uncertainty about the positions of the code word symbols at the decoder. In addition, we provide upper bounds on the capacity of binary noiseless intermittent communication with the help of a genie-aided encoder and decoder. The upper bounds imply a tradeoff between the capacity and the intermittency rate of the communication system, even if the receive window scales linearly with the code word length. [ABSTRACT FROM PUBLISHER]

Phase-coding method that embeds codewords into phase rather than intensity performs well for absolute phase retrieval. However, this method becomes instable when dealing with a large number of codewords. This paper designs three color phase-coding fringes to determine the fringe order pixel by pixel. Specifically, six groups of N -stairs are encoded into three coding fringes, and each group is endowed with a different color to eliminate ambiguity between groups. Such that three additional fringes can generate more than 6 N codewords by combining the color and phase information. Experiment results confirmed the validity of the proposed method. [ABSTRACT FROM AUTHOR]

In this paper, we further investigate the constructions on three-dimensional [ABSTRACT FROM AUTHOR]

In this paper, a new symmetric key cryptosystem based on linear codes is presented. Unlike most code-based cryptosystems, the code is known publicly. The encryption is based on randomly interleaving two codewords containing random errors. This is the first code-based cryptosystem based on random interleaving. The key size and security of the proposed scheme are analysed, and it is shown that allowing the code to be public results in a significantly smaller key than other code-based cryptosystems. Furthermore, it is proven that the best possible chosen plaintext attack does not affect the security. [ABSTRACT FROM AUTHOR]

Sparse code multiple access (SCMA) is one of the most promising methods among all the non-orthogonal multiple access techniques in the future 5G communication. Compared with some other non-orthogonal multiple access techniques, such as low density signature, SCMA can achieve better performance due to the shaping gain of the SCMA code words. However, despite the sparsity of the code words, the decoding complexity of the current message passing algorithm utilized by SCMA is still prohibitively high. In this paper, by exploring the lattice structure of SCMA code words, we propose a low-complexity decoding algorithm based on list sphere decoding (LSD). The LSD avoids the exhaustive search for all possible hypotheses and only considers signal within a hypersphere. As LSD can be viewed a depth-first tree search algorithm, we further propose several methods to prune the redundancy-visited nodes in order to reduce the size of the search tree. Simulation results show that the proposed algorithm can reduce the decoding complexity substantially while the performance loss compared with the existing algorithm is negligible. [ABSTRACT FROM PUBLISHER]

A technique was recently reported to construct high-rate variable-length constrained sequence codes. In this study, the authors outline an algorithm that simplifies the search procedure that is integral to that technique. This algorithm enables examination of a large search space limited only by length and/or number of codewords in order to determine codeword and sourceword lengths that result in high-rate codes. They also describe a straightforward approach to construct codewords and sourcewords of the required lengths in order to complete the design of instantaneously-decodeable capacity-approaching codes that satisfy the specified sequence constraints. They provide results that demonstrate the usefulness of this approach. [ABSTRACT FROM AUTHOR]

Snake-in-the-box codes under Kendall’s \tau -metric are studied in the rank modulation scheme for flash memories, where codewords are a subset of permutations in S_{n} with minimal Kendall’s \tau -distance two, and two cyclically consecutive codewords are connected via a push-to-the-top operation. Studies so far restrict the push-to-the-top operations only on odd indices, resulting in a snake consisting of permutations with the same parity, and thus, the minimal distance constraint is easily satisfied. Asymptotically optimal snake codes have been constructed this way in S2n+1 . As for S2n+2 , this framework keeps the last element fixed, and thus, a snake in S2n+2 is equivalent to a snake in S2n+1 , which is rather trivial. If one wants to do better, then it is inevitable to have some push-to-the-top operations on even indices, resulting in a combination of odd and even permutations in the snake, which increases the difficulty to guarantee the minimal Kendall’s $\tau $ -distance constraint. Thus, Horovitz and Etzion pose the open problem to prove or disprove that the size of the largest snake in ({1}/{4})|S_{2n+2}| . [ABSTRACT FROM PUBLISHER]

This paper presents a model for signal compression, which consists of a piecewise uniform quantizer and a new lossless coder. The model is designed in a general manner, i.e. for any symmetrical signal distribution; this general theory is applied to design models for Gaussian and Laplacian distributions. Rigorous mathematical derivation of the expression for the bit-rate is presented. Forward adaptation of the model is done for non-stationary signals. Theory is proved by simulations in MATLAB and by an experiment with a real speech signal. The most important advantages of the model are low complexity and good performances - it satisfies G.712 standard for the speech transmission quality with 6.18 bps (bits per sample), which is significantly smaller than 8 bps required for quantizers used in PSTN(public switched telephone network) defined with G.711 standard. [ABSTRACT FROM AUTHOR]

We say that an s-subset of codewords of a code X is ( s, l)- bad if X contains l other codewords such that the conjunction of these l words is covered by the disjunction of the words of the s-subset. Otherwise, an s-subset of codewords of X is said to be ( s, l)-bad. A binary code X is called a disjunctive ( s, l) cover-free (CF) code if X does not contain ( s, l)-bad subsets. We consider a probabilistic generalization of ( s, l) CF codes: we say that a binary code is an ( s, l) almost cover-free (ACF) code if almost all s-subsets of its codewords are ( s, l)-good. The most interesting result is the proof of a lower and an upper bound for the capacity of ( s, l) ACF codes; the ratio of these bounds tends as s→∞ to the limit value log e/( le). [ABSTRACT FROM AUTHOR]

Recently, a novel scheme to hide data into encrypted H.264/AVC videos using code-word substitution has been proposed by Xu et al. However, the statistical analysis of CAVLC code-words demonstrate that Xu et al.’s work does not fully exploit redundancy existing in CAVLC code-word for data embedding. In this paper, an improved version of Xu et al.’s data hiding method in encrypted H.264/AVC videos is proposed. Specifically, when suffixLength is equal to 1, data embedding is performed by paired code-word substitution. When suffixLength is greater than 2, not the single code-word substitution but the multiple-based notational system is adopted for data embedding. Experimental results have demonstrated that the improved method is indeed capable of providing a larger embedding capacity in comparison with Xu et al.’s method. Moreover, both encryption and data embedding can be accomplished without affecting the coding efficiency of H.264/AVC by keeping exactly the same bitrate. [ABSTRACT FROM AUTHOR]

For any affine-variety code we show how to construct an ideal whose solutions correspond to codewords with any assigned weight. We are able to obtain geometric characterizations for small-weight codewords for some families of Hermitian codes over any F q 2 . From these geometric characterizations, we obtain explicit formulas. In particular, we determine the number of minimum-weight codewords for all Hermitian codes with d ≤ q and all second-weight codewords for distance- 3 , 4 codes. [ABSTRACT FROM AUTHOR]

Equidistant subspace codes are studied. A classification of the largest 1-intersecting codes in PG ( 5 , 2 ) , whose codewords are planes, is provided. Also, new constructions of large equidistant codes are presented. [ABSTRACT FROM AUTHOR]

We establish upper and lower bounds on the secrecy capacity of the degraded Gaussian diamond–wiretap channel, and identify several ranges of channel parameters where these bounds coincide with useful intuitions. Furthermore, we investigate the effect of the presence of an eavesdropper on the capacity. We consider the following two scenarios: 1) common randomness is available at the source and the two relays and 2) randomness is available only at the source, and there is no randomness at the relays. Our upper bounds are established by taking into account the correlation between the two relay signals and the available randomness at the encoders, which generalize the techniques recently developed for the case without secrecy constraint. For the lower bounds, we propose two types of coding schemes: 1) decode-and-forward schemes where the relays cooperatively transmit the message and the fictitious message and 2) partial decode-and-forward schemes incorporated with multicoding in which each relay sends an independent partial message and the whole or partial fictitious message using dependent codewords. [ABSTRACT FROM AUTHOR]

The well-known Huffman algorithm is an elegant approach to solve the basic problem of finding the optimal code among those with Kraft sums smaller than or equal to 1. In this paper, an extended problem is investigated, where the Kraft sum of the usable codes is limited to a given real number $\gamma $ , $0<\gamma <1$ . Unlike the case $\gamma =1$ (i.e., Huffman coding), for $\gamma <1$ , the Kraft sum of the optimal code is not necessarily equal to $\gamma $ . However, we show that the Kraft sum of the optimal code lies in a finite set of rational numbers which depend on the value of $\gamma $ . This motivates us to first devise a recursive algorithm to obtain the optimal codelengths with Kraft sum equal to $\gamma '$ , where $\gamma '$ has a finite binary representation and $0<\gamma '<1$ . To do so, the set of $N$ -tuple codelength vectors with a specific Kraft sum $\gamma '$ is characterized. The binary representation of $\gamma $ plays a fundamental role in all problems that arise for $\gamma <1$ . [ABSTRACT FROM PUBLISHER]

In this work, we propose structured root-low-density parity-check (LDPC) codes and design techniques for block-fading channels. In particular, quasi-cyclic root-LDPC codes, irregular repeat-accumulate root-LDPC codes and controlled doping root-LDPC codes based on progressive edge growth (PEG) techniques for block-fading channels are proposed. The proposed root-LDPC codes are both suitable for channels under F=2,3 and 4 independent fading per codeword. The performance of the proposed codes is investigated in terms of frame error rate (FER). The proposed root-LDPC codes are capable of achieving the channel diversity and outperform standard LDPC codes. For block-fading channel with F=2 our proposed PEG-based root-LDPC codes outperform PEG-based LDPC codes by 7.5 dB at a FER close to 10. [ABSTRACT FROM AUTHOR]

In this paper, a novel code-shifting technique, which can be added atop asynchronous incoherent optical code-division multiple-access systems without complex modifications, is proposed and studied. The new technique divides the time-slot (or chips), in which the optical pulses of codewords are located, into $g$ equal-width sub-chips; every pulse is randomly and independently shifted to start at one of the $g$ sub-chips of its own chip, where $g > 1$ is a positive integer. The effects of this random $g$-shift to the cross-correlation property and performance of asynchronous optical codes (of periodic cross-correlation functions of at most one) are formulated. Although it is found that the periodic cross-correlation functions are worsened to $3-2/g$, our theoretical and computer-simulation results show an unconventional finding that code performance improves as $g$ increases. [ABSTRACT FROM PUBLISHER]

This paper studies variable-length (VL) source coding of general sources with side-information. Novel one-shot coding bounds for Slepian–Wolf (SW) coding, which give nonasymptotic tradeoff between the error probability and the codeword length of VL-SW coding, are established. One-shot results are applied to asymptotic analysis, and a general formula for the optimal coding rate achievable by weakly lossless VL-SW coding (i.e., VL-SW coding with vanishing error probability) is derived. Our general formula reveals how the encoder side-information and/or VL coding improve the optimal coding rate in the general setting. In addition, it is shown that if the encoder side-information is useless in weakly lossless VL coding then it is also useless even in the case where the error probability may be positive asymptotically. [ABSTRACT FROM AUTHOR]

Effective and efficient background subtraction is important to a number of computer vision tasks. In this paper, we introduce a new background model that integrates several new techniques to address key challenges for background modeling for moving object detection in videos. The novel features of our proposed Self-adaptive CodeBook (SACB) background model are: a more effective color model using YCbCr color space, a statistical parameter estimation method, and a new algorithm for adding new background codewords into the permanent model and deleting noisy codewords from the models. Also, a new block-based approach is introduced to exploit the local spatial information. The proposed model is rigorously tested and has shown significant performance improvements over several previous models. [ABSTRACT FROM AUTHOR]

A code is called transitive if its automorphism group (the isometry group) of the code acts transitively on its codewords. If there is a subgroup of the automorphism group acting regularly on the code, the code is called propelinear. Using Magma software package we establish that among 201 equivalence classes of transitive perfect codes of length 15 from Östergård and Pottonen (2009) there is a unique nonpropelinear code. We solve the existence problem for transitive nonpropelinear perfect codes for any admissible length n , n ≥ 15 . Moreover we prove that there are at least 5 pairwise nonequivalent such codes for any admissible length n , n ≥ 255 . [ABSTRACT FROM AUTHOR]

In this paper, we study the minimum/stopping distance of array low-density parity-check (LDPC) codes. An array LDPC code is a quasi-cyclic LDPC code specified by two integers \(q\) and \(m\) , where \(q\) is an odd prime and \(m \leq q\) . In the literature, the minimum/stopping distance of these codes (denoted by \(d(q,m)\) and \(h(q,m)\) , respectively) has been thoroughly studied for \(m \leq 5\) . Both exact results, for small values of \(q\) and \(m\) , and general (i.e., independent of \(q\) ) bounds have been established. For \(m=6\) , the best known minimum distance upper bound, derived by Mittelholzer, is \(d(q,6) \leq 32\) . In this paper, we derive an improved upper bound of \(d(q,6) \leq 20\) and a new upper bound \(d(q,7) \leq 24\) by using the concept of a template support matrix of a codeword/stopping set. The bounds are tight with high probability in the sense that we have not been able to find codewords of strictly lower weight for several values of \(q\) using a minimum distance probabilistic algorithm. Finally, we provide new specific minimum/stopping distance results for \(m \leq 7\) and low-to-moderate values of \(q \leq 79\) . [ABSTRACT FROM AUTHOR]

Bidirectional decoding improves the error resilience of the fix-free codes, which is important in some applications like video coding. However, in general, two separate decoders must be designed for forward and backward decoding and hence, the cost of decoding is almost doubled. For the symmetric fix-free codes, although the forward and backward decoders are the same, the redundancy could be much greater than the case of asymmetric fix-free codes. In this paper, a class of fix-free codes, called weakly symmetric, is studied. A code is weakly symmetric if the reverse of each codeword itself is a codeword. This imposes a much weaker constraint on the codewords than what is necessitated by the symmetric codes, i.e., each codeword must be equal to its reverse. We show that the forward and backward decoders of a weakly symmetric fix-free code are essentially the same. In addition, it is shown that two significant sufficient conditions for the existence of asymmetric fix-free codes are also applicable to the case of weakly symmetric fix-free codes. As a result, we conclude that for any memoryless source, the redundancy of the optimal weakly symmetric fix-free code is at most 1.0817 bits. Moreover, it can be only 0.8 bit greater than the redundancy of the Huffman code in the worst case. In summary, weakly symmetric fix-free codes can be regarded as an option by which one can to some extent achieve the low redundancy of asymmetric fix-free codes and the low-cost bidirectional decoding of symmetric fix-free codes, simultaneously. [ABSTRACT FROM AUTHOR]

This paper presents lossless prefix codes optimized with respect to a payoff criterion consisting of a convex combination of maximum codeword length and average codeword length. The optimal codeword lengths obtained are based on a new coding algorithm, which transforms the initial source probability vector into a new probability vector according to a merging rule. The coding algorithm is equivalent to a partition of the source alphabet into disjoint sets on which a new transformed probability vector is defined as a function of the initial source probability vector and scalar parameter. The payoff criterion considered encompasses a tradeoff between maximum and average codeword length; it is related to a payoff criterion consisting of a convex combination of average codeword length and average of an exponential function of the codeword length, and to an average codeword length payoff criterion subject to a limited length constraint. A special case of the first related payoff is connected to coding problems involving source probability uncertainty and codeword overflow probability, whereas the second related payoff compliments limited length Huffman coding algorithms. [ABSTRACT FROM AUTHOR]

We consider the problem of coded communication, where in each time frame, the transmitter is either silent or transmits a codeword from a given (randomly selected) codebook. The task of the decoder is to decide whether transmission has taken place, and if so, to decode the message. We derive the optimum detection/decoding rule in the sense of the best tradeoff among the probabilities of decoding error, false alarm, and misdetection. For this detection/decoding rule, we then derive single-letter characterizations of the exact exponential rates of these probabilities for the average code in the ensemble. It is shown that previously proposed decoders are in general strictly suboptimal. [ABSTRACT FROM AUTHOR]

This is a survey of the origin, current progress and applications of a major roadblock to the development of analytic models for DNA computing (a massively parallel programming methodology) and DNA self-assembly (a nanofabrication methodology), namely the so-called CODEWORD DESIGN problem. The problem calls for finding large sets of single DNA strands that do not crosshybridize to themselves or to their complements and has been recognized as an important problem in DNA computing, self-assembly, DNA memories and phylogenetic analyses because of their error correction and prevention properties. Major recent advances include the development of experimental techniques to search for such codes, as well as a theoretical framework to analyze this problem, despite the fact that it has been proven to be NP-complete using any single concrete metric space to model the Gibbs energy. In this framework, codeword design is reduced to finding large sets of strands maximally separated in DNA spaces and, therefore, the key to finding such sets would lie in knowledge of the geometry of these spaces. A new general technique has been recently found to embed them in Euclidean spaces in a hybridization-affinity-preserving manner, i.e., in such a way that oligos with high/low hybridization affinity are mapped to neighboring/remote points in a geometric lattice, respectively. This isometric embedding materializes long-held metaphors about codeword design in terms of sphere packing and error-correcting codes and leads to designs that are in some cases known to be provably nearly optimal for some oligo sizes. It also leads to upper and lower bounds on estimates of the size of optimal codes of size up to 32-mers, as well as to infinite families of solutions to CODEWORD DESIGN, based on estimates of the kissing (or contact) number for sphere packings in Euclidean spaces. Conversely, this reduction suggests interesting new algorithms to find dense sphere packing solutions in high dimensional spheres using results for CODEWORD DESIGN previously obtained by experimental or theoretical molecular means, as well as a proof that finding these bounds exactly is NP-complete in general. Finally, some research problems and applications arising from these results are described that might be of interest for further research. [ABSTRACT FROM AUTHOR]

The Count Compatible Pattern Run-Length (CCPRL) coding compression method is proposed to further improve the compression ratio. Firstly, a segment of pattern in the test set is retained. Secondly, don't-care bits are filled so as to make subsequent patterns compatible with the retained pattern for as many times as possible until it can no longer be made compatible. Thirdly, the compatible patterns are represented by symbol '0' (equal) and symbol '1' (contrary) in the codeword. In addition, the number of consecutive compatible patterns is counted and expanded into binary which indicates when the codeword ends. At last, the six largest ISCAS'89 benchmark circuits verify the proposed method, the experimental results show that the average compression ratio achieved is up to 71.73 %. [ABSTRACT FROM AUTHOR]

Growing test data volume and excessive test application time are two serious concerns in scan-based testing for SoCs. This paper presents an efficient test-independent compression technique based on block merging and eight coding (BM-8C) to reduce the test data volume and test application time. Test compression is achieved by encoding the merged blocks after merging consecutive compatible blocks with exact eight codewords. The proposed scheme compresses the pre-computed test data without requiring any structural information of the circuit under test. Therefore, it is applicable for IP cores in SoCs. Experimental results demonstrate that the BM-8C technique can achieve an average compression ratio up to 68.14 % with significant low test application time. [ABSTRACT FROM AUTHOR]

One of the most famous and investigated lossless data-compression schemes is the one introduced by Lempel and Ziv about 30 years ago [IEEE Trans. Inform. Theory, 23 (1977), pp. 337--343]. This compression scheme is known as "dictionary-based compressor" and consists of squeezing an input string by replacing some of its substrings with (shorter) codewords which are actually pointers to a dictionary of phrases built as the string is processed. Surprisingly enough, although many fundamental results are nowadays known about the speed and effectiveness of this compression process, "we are not aware of any parsing scheme that achieves optimality...under any constraint on the codewords other than being of equal length" [N. Rajpoot and C. Sahinalp, in Handbook of Lossless Data Compression, Academic Press, New York, 2002, p. 159]. Here optimality means to achieve the minimum number of bits in compressing each individual input string without any assumption on its generating source. In this paper we investigate some issues pertaining to the bit-complexity of LZ77-based compressors, the most powerful variant of the LZ-compression scheme, and we design algorithms which achieve bit-optimality in the compressed output size by taking efficient/optimal time and optimal space. [ABSTRACT FROM AUTHOR]

This study examines the code words and euphemisms which protected Anglo-American communications intelligence (Comint) during the Cold War. It explains how the code word security system operated and identifies the main Comint code words and euphemisms in effect from 1946 to 1999. The article then uses these code words and euphemisms to interpret declassified American documents and reveal more information about Anglo-American Comint on the Congo, Bolivia, Indonesia, South Vietnam and China in the 1960s. [ABSTRACT FROM PUBLISHER]

Abstract: Recently, a large number of results have appeared on the small weights of the (dual) linear codes arising from finite projective spaces. We now focus on the large weights of these linear codes. For q even, this study for the code reduces to the theory of minimal blocking sets with respect to the k-spaces of , odd-blocking the k-spaces. For q odd, in a lot of cases, the maximum weight of the code is equal to , but some unexpected exceptions arise to this result. In particular, the maximum weight of the code turns out to be . In general, the problem of whether the maximum weight of the code , with (), is equal to , reduces to the problem of the existence of sets of points in intersecting every k-space in points. [Copyright &y& Elsevier]

Steiner systems S(2 − 1, 3, 2) of rank 2 − m+1 over the field $$\mathbb{F}_2$$ are considered. A new recursive method for constructing Steiner triple systems of an arbitrary rank is proposed. The number of all Steiner systems of rank 2 − m+1 is obtained. Moreover, it is shown that all Steiner triple systems S(2 − 1, 3, 2) of rank r ≤ 2 − m+1 are derived, i.e., can be completed to Steiner quadruple systems S(2, 4, 3). It is also proved that all such Steiner triple systems are Hamming; i.e., any Steiner triple system S(2 − 1, 3, 2) of rank r ≤ 2 − m + 1 over the field $$\mathbb{F}_2$$ occurs as the set of words of weight 3 of a binary nonlinear perfect code of length 2−1. [ABSTRACT FROM AUTHOR]

A distance-preserving mapping is a one-to-one function f from p-ary vectors of length m to q-ary vectors of length n such that any two distinct p-ary vectors are mapped to two different q-ary vectors with an equal or greater Hamming distance. A distance-increasing mapping is a special distance-preserving mapping which strictly increases the distance by at least one if the distance of two distinct input vectors is less than the length of the output vectors. A constant composition code over a k-ary alphabet has the property that the numbers of occurrences of the k symbols within a codeword are fixed for each codeword. One of the most important applications of distance-preserving mappings and distance-increasing mappings is to construct constant composition codes, of which the permutation codes are a special subclass. There are two results in this paper. First, we propose a swap-based distance-increasing mapping from binary vectors to quaternary constant composition vectors. Second, we prove that it is impossible to construct any swap-based distance-preserving mappings from binary vectors to ternary constant composition vectors under the swap model that we defined. [ABSTRACT FROM AUTHOR]

In this paper, the asymptotic growth rate of the weight distribution of irregular doubly generalized LDPC (D-GLDPC) codes is derived. The analysis yields a compact expression which accurately approximates the growth rate function for the case of small linear-weight codewords. This paper generalizes existing results for LDPC and generalized LDPC (GLDPC) codes. Ensembles with smallest check or variable node minimum distance greater than 2 are shown to have good growth-rate behavior, while for other ensembles a fundamental parameter is identified which discriminates between an asymptotically small and an asymptotically large expected number of small linear-weight codewords. Also, in the latter case it is shown that the growth rate depends only on the check and variable nodes with minimum distance 2. An important connection between this new result and the stability condition of D-GLDPC codes over the BEC is highlighted. Such a connection, previously observed for LDPC and GLDPC codes, is now extended to the case of D-GLDPC codes. Finally, it is shown that the analysis may be extended to include the growth rate of the stopping set size distribution of irregular D-GLDPC codes. [ABSTRACT FROM AUTHOR]

Due to the low peak-to-mean envelope power ratio (PMEPR) of Golay sequences together with their connection to generalized Reed-Muller codes, many authors have proposed using Golay sequences as codewords in orthogonal frequency-division multiplexing (OFDM). Golay sequences that unexpectedly share the same aperiodic autocorrelation function can be used to construct longer Golay sequences. We study the shared autocorrelation property of general sequences with the ultimate goal of using those results to find other low power sequences. In this paper, we provide several new constructions of families of pairs of sequences with the shared autocorrelation property that enable us to explain nearly all of the binary shared autocorrelation property for sequences of lengths up to 24. [ABSTRACT FROM AUTHOR]

An (r, δ, ε)-locally decodable code encodes a k-bit message x to an N-bit codeword C(x), such that for every i ∈ [k], the ith message bit can be recovered with probability 1 -- ε, by a randomized decoding procedure that queries only r bits, even if the codeword C(x) is corrupted in up to δN locations. Recently a new class of locally decodable codes (LDCs), based on families of vectors with restricted dot products, has been discovered. We refer to those codes as matching vector (MV) codes. Several families of (r, δ,Θ(rδ))-locally decodable MV codes have been obtained. While codes in those families were shorter than codes of earlier generations, they suffered from having large values of ε = Ω(rδ), which meant that r-query MV codes could only handle error rates below 1/r. Thus larger query complexity gave shorter length codes but at the price of less error tolerance. No MV codes of a superconstant number of queries capable of tolerating a constant fraction of errors were known to exist. In this paper we present a new view of matching vector codes and uncover certain similarities between MV codes and classical Reed-Muller (RM) codes. Our view allows us to obtain deeper insights into the power and limitations of MV codes. Specifically, we obtain the following: (1) We show that existing families of MV codes can be enhanced to tolerate a large constant fraction of errors, independent of the number of queries. Such enhancement comes at a price of a moderate increase in the number of queries. (2) Our construction yields the first families of MV codes of superconstant query complexity that can tolerate a constant fraction of errors. Our codes are shorter than RM LDCs for all values of r ≤ log k/(loglog/c)c, for some constant c. (3) We show that any MV code encodes messages of length k to codewords of length at least k2Ω(√ log k. Therefore MV codes do not improve upon RM LDCs for r ≥ (log k)Ω(√ log k. [ABSTRACT FROM AUTHOR]