A new class of twinSudokutables (TSTs) is presented. These tables can be divided into both$s \times d$and$d \times s$subtables. They are constructed using the cyclotomic cosets of$Z_n$via two distinct vectors of cyclotomic coset elements and their Kronecker product. We prove that it is possible to generate$m$TSTs that are strongly mutually distinct (SMD), i.e., for every$0\leq i, j \leq m-1$, the$(i,j)$th entry of the tables contains different symbols. We also provide a method to construct$m$different TSTs that can be converted into twin solidSudokutables (TSSTs) as a perfect set of SMD TSSTs in order to make triplet solidSudokucubes (TSSCs). These TSSCs are symmetric cubes so that a cut from any of the six faces is a TSST. As a result, new twinSudokupuzzles (TSPs) and SMDTSPs are obtained that can be used to design new types ofSudokugames.

A new method of constructing Sudoku tables (STs) (Sudoku Latin squares) is introduced by making use of individual vectors of cyclotomic cosets of Zn, and their Kronecker product. We show that, it is possible to construct m different STs of order m such that for every 0 ≤ u, v ≤ m - 1 the (u, v)-entry of these m STs is different. These STs could be considered as a perfect set of strongly mutually distinct (SMD) STs, which in turn are used to construct a solid Sudoku cube (SSC). As a result, a new version of SMD Sudoku puzzles under a new rule and condition is introduced that are interesting for Sudoku puzzles game designers.

Locally repairable codes (LRC) have been studied from two approaches to locally repair multiple failed nodes: 1) parallel approach, in which a coordinate i of an [n,k,d] linear code is said to have locality r and availability t if there exist t disjoint repair sets each of which contains at most r other coordinates that can recover the value of the i -th coordinate; 2) sequential approach, in which the erased symbols (failed nodes) are repaired, one by one, and any previously repaired node can be used to repair the remaining failed nodes. In this paper, we first consider LRC aiming at joint sequential-parallel repairing multiple failed nodes, and study the (n,k,r,t,u) -ELRCs (Exact locally repairable codes) which are [n,k] linear codes with the property that any set of failed nodes of size at most t can be simultaneously repaired in parallel mode, and each element of a set E of failed nodes of size at most u can be sequentially repaired by r (r<; k) other coordinates. We present a method by which with a given parity-check matrix of an (n,k,r,t,u) -ELRC with minimum Hamming distance d, a new ELRC with minimum Hamming distance 2d and availability t+1 is constructed that can repair each set of failed nodes E of size at most 2u+1 in sequential mode and this repair is done in at most u-t+2 steps. We construct a big family of LRCs by making use of orthogonal Latin rectangles and permutation cubes and some other combinatorial designs; the constructed codes contain the family of direct product codes; we also use m -dimensional permutation cubes to construct LRCs with short block length for each r.

Tandem duplication (TD) errors occur when data is stored in the DNA of living organisms. The construction of codes to correct these errors was previously considered. A method was proposed to construct codes for TD errors of length at most k , , based on the uniqueness of ‐roots. It was shown that there exist words which have more than one ‐root when . As a consequence, the previous approach to correcting TD errors of length at most k cannot be extended to . In this study, ‐hinge‐free irreducible words are introduced and used to construct codes for TD errors of length at most k where . Furthermore, it is conjectured that the proposed approach can be extended to .

A linear network (LN) code can be described by either global encoding kernels (GEKs) or local encoding kernels (LEKs). In the literature, the multicast property of an LN code is described using GEKs, so the design algorithms for multicast LN codes employ GEKs to check this property. In this paper, a criterion is developed so that LEKs rather than GEKs can be used to check the multicast maximum distance separable (MDS) property of linear network error correction (LNEC) codes on erroneous networks. Further, it is used to develop a design algorithm for multicast MDS LNEC codes on erroneous cyclic networks. This algorithm is more efficient than the algorithm that uses GEKs when the number of edges is high and the interconnection of these edges is low.

Recently, the refined singleton bound over acyclic networks was extended to convolutional error-correcting network codes over cyclic networks using extended coding vectors. In this paper, it is shown that constructing an MDS code is equivalent to constructing a multicast code. This is used to develop an algorithm for constructing MDS field-based codes over acyclic networks when the sinks know the topology of the network and the network coding employed at all nodes. A lower bound is given on the size of the field required for the algorithm to be successful. Then this algorithm is extended to construct MDS convolutional error-correcting codes over cyclic networks. The complexity of the proposed algorithm is evaluated.

In this study, the authors study ring‐based linear network coding over erroneous cyclic networks over commutative rings such as a principal ideal domain or discrete valuation ring. In the first part, they study coherent field‐based linear error‐correcting network codes (LENCs) over cyclic networks. By changing alphabet symbols from fields to commutative rings, they extend Zhang's formulation for LENCs restricted on acyclic networks to cyclic networks, and generalise fundamental results and concepts such as the minimum rank distance and the refined Singleton bound, and show that this bound is tight. In the second part, they generalise some main results such as the free distance and the generalised Singleton bound from convolutional codes to ring‐based LENCs over cyclic networks. In the third part, they propose an algebraic method for calculating sink bit error probability of ring‐based linear network codes over all erroneous networks by using the authors’ formulations.

In this paper, a new secure channel coding scheme is presented which randomly inserts and deletes bits in a codeword of a quasi‐cyclic‐low‐density parity check (QC‐LDPC) code. It is shown that the key size is smaller than other code‐based cryptosystems based on permutation and scrambling matrices. The positions of the inserted and deleted bits are determined using a secret key. It is shown that the error performance of the resulting code after the insertions and deletions is better than a random low‐density parity check code with similar parameters. An important advantage of this cryptosystem is that even if the QC‐LDPC code is revealed, the system remains secure. Furthermore, the proposed approach using insertions and deletions can be employed with other classes of error correcting codes.

This study considers the construction of four‐cycle free quasi‐cyclic low‐density parity‐check (QC‐LDPC) codes. These codes are based on the cyclotomic cosets of q modulo n where q is a prime power, n is a prime and ( n , q ) = 1. If s is the order of q modulo n , then n − 1 = sl for some integer l . Then there are l distinct cyclotomic cosets , 1 ≤ i ≤ l . Concatenation of the l circulant matrices formed using these sets gives an s × sl matrix M co ( n , q ). In addition, the Kronecker product of the transpose of ∪ i with itself modulo n gives an sl × sl matrix M kr ( n , q ). Replacing the entries of these matrices with their associated dispersed binary n × n matrices provides binary QC‐LDPC codes with girth at least six. Furthermore, for any prime power q ′ such that q ′ = n + 1 or q ′ ≥ 2 n , these two matrices can be used to construct q ′‐ary QC‐LDPC codes with girth at least six. These constructions produce large classes of four‐cycle free binary and non‐binary QC‐LDPC codes. Among the structured LDPC codes, the introduced technique, from code‐construction‐complexity perspective, which is an engineering factor, is at least among the best ones if not the best. Performance results are presented which show that the codes obtained perform well over additive white Gaussian noise channel with the iterative sum‐product decoding algorithm.

In this study, a method is presented to construct column weight 3 (CW3) low‐density parity‐check (LDPC) codes using three‐partite graphs. Let G b be a bipartite graph and N g be the set of all minimum length cycles in G b . Using G b and N g , a three‐partite graph denoted G ( G b , N g ), or simply G t , is formed. Let T be the set of length 3 cycles in G t and T a be the set of three element subsets of vertices in G t such that each of these subsets form a subgraph with no edges in G t and has precisely one element in each section of G t . Furthermore, let H be the binary matrix in which the set of rows represent the set of vertices of G t , the columns represent the elements of V := T ∪ T a , and h ij = 1 if and only if the i th vertex of G t belongs to the j th three element set in V . Then H is a CW3 binary matrix. Using the Tanner graph representing H , a recursive construction for CW3 LDPC codes is provided. Applying a simple restriction on T and T a , codes free of length 4 cycles are generated. Euclidean and finite geometry codes are used as the base codes for generating new CW3 LDPC codes. Results are presented which show that these new codes perform well in an additive white Gaussian noise (AWGN) channel with the iterative sum‐product decoding algorithm.

A new joint cryptography‐channel coding technique is introduced which employs punctured quasi‐cyclic‐low density parity check (QC‐LDPC) codes obtained from extended difference families. The absence of permutation and scrambling matrices reduces the key size compared with similar code‐based cryptosystems, while having an acceptable level of security. The main advantage of this system is that, provided the system parameters are chosen appropriately, even if the code employed is revealed the system remains secure. Performance results are presented which show that the punctured code outperforms a random low density parity check (LDPC) code of the same length and rate.

A finite set system (FSS) is a pair ( V , ℬ) where V is a finite set whose members are called points, equipped with a finite collection of its subsets ℬ whose members are called blocks. In this paper, FSSs are used to define a class of quasi‐cyclic low‐density parity‐check (LDPC) codes, called FSS codes, such that the constructed codes possess large girth and arbitrary column‐weight distributions. Especially, the constructed column weight‐2 FSS codes have higher rates than the column weight‐2 geometric and cylinder‐type codes with the same girths. To find the maximum girth of FSS codes based on ( V , ℬ), inevitable walks are defined in ℬ such that the maximum girth is determined by the smallest length of the inevitable walks in ℬ. Simulation results show that the constructed FSS codes have very good performance over the additive white Gaussian noise channel with iterative decoding and achieve significantly large coding gains compared with the random‐like LDPC codes of the same lengths and rates.

Reverberation is a major problem for time delay estimation (TDE) in enclosed environments. In this paper, a robust TDE method based on the generalized cross-correlation (GCC) is proposed. An efficient preprocessing technique to calculate the all-pass component is introduced to improve the performance of GCC-based techniques in reverberant conditions. Performance results are given which demonstrate that the proposed approach provides better performance for a wide range of microphone locations and reverberation times. Results in real acoustic environments confirm the effectiveness of the proposed TDE method. Compared to other TDE methods, our solution has low computational complexity and can be employed in real-time applications.

This paper presents a single-microphone approach to the enhancement of noisy reverberant speech via inverse filtering and spectral processing. An efficient algorithm is used to blindly estimate the inverse filter of the Room Impulse Response (RIR). This filter is used to attenuate the early reverberation. A simple technique to blindly determine the filter length is presented. A two-step spectral subtraction method is proposed to efficiently reduce the effects of background noise and the residual reverberation on the equalized impulse response. In general, the equalized impulse response has two detrimental effects, late impulses and pre-echoes. For the late impulses, an efficient spectral subtraction algorithm is developed which introduces only minor musical noise. Then a new algorithm is introduced which reduces the remaining pre-echo effects. The performance of this two-stage method is examined in different reverberant conditions including real environments. It is also evaluated with white Gaussian and recorded babble noise. The results obtained demonstrate that the proposed blind method is superior in terms of reducing early and late reverberation effects and noise compared to well known single-microphone techniques in the literature.

This paper presents a novel iterative hard decision decoding algorithm for binary linear block codes over a binary symmetric channel (BSC). The problem is formulated as a 0-1 integer programming problem which is known to be NP-hard. When the crossover probability c of the channel is known, the solution space of the decoding problem can be decreased to a sphere whose radius is related to c. Using the penalty function method, the problem is reformulated on this reduced solution space. Then an iterative multi-flip local search algorithm is designed to find the global solution of this decoding problem. For a code with minimum distance d, when the radius of the sphere is not greater than d-1/2, this algorithm has the maximum likelihood (ML) certificate property, i.e., if the decoder outputs a codeword, it is guaranteed to be the ML codeword. Compared to the probabilistic suboptimal iterative belief propagation (BP) decoder, this approach has lower complexity and better performance. Numerical results show that in terms of speed and performance the proposed decoding method outperforms BP decoding in the error floor region.

A new combinatorial technique for constructing girth-6 structured binary regular low-density parity-check (LDPC) codes based on special types of t-designs is given. A very large number of well-known t-designs can be used by this method for code construction. Based on this method, a t-(v,k,λ) design D=(X,B) can be exploited for code construction if it satisfies the following three conditions: 1) |B1 ∩ B2|≤ t for any two blocks B1,B2∈ B and B1≠ B2; 2) λ>1; and 3) k>t. Though the technique works for any t-design satisfying these conditions, we focus only on the utilization of simple triple systems, super-simple BIBDs, Steiner systems, and large sets (LSs) of t-designs. We also construct binary and non-binary girth-6 QC-LDPC codes from the t-designs satisfying these conditions by using matrix dispersion method. Experimental results show that the constructed non-binary QC-LDPC codes can provide good practical performance under iterative decoding using the fast Fourier transform based q-ary sum-product algorithm (FFT-QSPA) and they can achieve acceptable coding gains over random-like codes of comparable parameters decoded with sum-product algorithm (SPA).

In this paper, we propose a speech-model based method using the linear predictive (LP) residual of the speech signal and the maximum-likelihood (ML) estimator proposed in “Blind estimation of reverberation time,” (R. Ratnam , J. Acoust. Soc. Amer., 2004) to blindly estimate the reverberation time (RT60). The input speech is passed through a low order linear predictive coding (LPC) filter to obtain the LP residual signal. It is proven that the unbiased autocorrelation function of this LP residual has the required properties to be used as an input to the ML estimator. It is shown that this method can successfully estimate the reverberation time with less data than existing blind methods. Experiments show that the proposed method can produce better estimates of RT60, even in highly reverberant rooms. This is because the entire input speech data is used in the estimation process. The proposed method is not sensitive to the type of input data (voiced, unvoiced), number of gaps, or window length. In addition, evaluation using white Gaussian noise and recorded babble noise shows that it can estimate RT60in the presence of (moderate) background noise.

This paper presents a method based on higher order statistics (HOS), namely the normalized third-order moment (skewness), for blind estimation of the inverse filter of the room impulse response (RIR). Skewness is used as a measure of asymmetry, and a comprehensive comparison with the commonly used metric (kurtosis) is presented. It is shown that a sufficiently long linear predictive (LP) residual of the speech signal has an asymmetric pdf with sufficient skewness to be used as a score function for the HOS-based approach. The proposed algorithm is optimized for the inverse filter estimation problem. This optimization includes an efficient initialization for high reverberation intensities, enabling the method to be employed in highly reverberant rooms. The direct-to-reverberation ratio (DRR) as well as the equalized impulse response clearly show that our method can estimate the inverse filter even in highly reverberant environments. In addition, performance results using recorded background noise and in time-varying environments illustrate that our approach is applicable in real world situations. The proposed method is shown to be superior to the method by Wu and Wang, particularly in terms of reducing the coloration effect. Experiments under different acoustic conditions confirm the effectiveness of the proposed method for time delay estimation (TDE). Finally, the proposed algorithm is used as the first-stage of monaural segregation, and it is shown to improve the performance under different conditions.

Difference sets are used to give a novel method for constructing structured regular quasi-cyclic low-density parity-check codes. Let Fqbe a field with q elements and assume that D={d1,..., dk} is a (v,k,1)-difference set for Zvwith d12k. Depending on v=q-1, v≥ 2dkor v≥ 2dk-1, three code construction methods are given that produce regular 4-cycle free codes, that is codes with girth at least 6. Simulation results show that the constructed codes perform well over the AWGN channel with an iterative sum-product message-passing decoding algorithm.

This paper presents a novel method for constructing structured regular low-density parity-check (LDPC) codes based on a special type of combinatorial designs, known as Steiner systems. This code design approach can be considered as a generalization of the well-known method which uses the point-block incidence matrix of a Steiner 2-design for the code construction. Though the given method can be applied on any Steiner system S(t, k, v), in this paper we focus only on Steiner systems with t ≥ 3. Furthermore, we show that not only a Steiner system (X,B) itself, but also its residual design with respect to an arbitrary point x ∈ X can be employed for code construction. We also present a technique for constructing binary and non-binary QC-LDPC codes from Steiner systems. The Tanner graph of the constructed codes is free of 4-cycles and hence the codes have girth at least six. Simulation results show that the so constructed codes perform well over the AWGN channel with iterative message-passing decoding.

A new class of high rate Fibonacci polynomial based error-correcting codes is introduced. For integers m; n; x ≥ 1, a square encoding matrix Q2mn(x) of order 2m and the corresponding decoding matrix Q2m-n(x) are provided. It is shown that a higher code rate is obtained than with the original Fibonacci polynomial based codes.

For q an odd prime and 1≤ m ≤ q, two specific binary qm × q2parity-check matrices denoted by HP(m, q) and HI(m, q) are considered. The corresponding binary codes, CP(m, q) and CI(m, q), respectively, are called proper and improper array codes with parameters m and q. Given a parity-check matrix H representing a binary code C, let s(H) denote the stopping distance of H and d(C) be the minimum Hamming distance of C. It is known that that s(HI(m, q)) = s(HP(m, q)) = d(CI(m, q)) = d(CP(m, q)) for m ≤ 3. In this paper, we show that these equalities do not hold for all values of m and q. In particular, although s(HP(4, 7)) = d(CP(4, 7)) = 8 we have s(HI(4, 7)) = 9 and d(CI(4, 7)) = 10. It is also shown that s(HP(5,1))dCP(5, 11)) = 10 while s(HI(5,11)) = 11 and d(CI(5, 11)) = 12. This suggests that in many cases the improper array codes would perform better than the proper array codes over the AWGN and binary erasure channels. Performance results are given which confirm this claim. The combinatorial structure of the eight-element stopping sets for H(m ≥ 4,q >; 5) is also determined.

This paper presents a low-complexity recursive and systematic method to construct good well-structured low-density parity-check (LDPC) codes. The method is based on a recursive application of a partial Kronecker product operation on a given gamma x q, q ges 3 a prime, integer lattice L(gamma x q). The (n - 1)- fold product of L(gamma x q) by itself, denoted Ln(gamma x q), represents a regular quasi-cyclic (QC) LDPC code, denoted (see PDF), of high rate and girth 6. The minimum distance of (see PDF) is equal to that of the core code (see PDF) introduced by L(gamma x q). The support of the minimum weight codewords in (see PDF) are characterized by the support of the same type of codewords in (see PDF). From performance perspective the constructed codes compete with the pseudorandom LDPC codes.

For q an odd prime and 1 les m les q, we study two binary qm times q2parity check matrices for binary array codes. For both parity check matrices, we determine the stopping distance and the minimum distance of the associated code for 2 les m les 3, and for (m, q)=(4, 5). In the case (m, q)=(4, 7), the stopping distance and the related minimum distance are also determined for one of the given parity check matrices. Moreover, we give a lower bound on the stopping distances for m > 3 and q > 3.

A new low-complexity generating method is given for the construction of long low-density parity-check (LDPC) codes. The method is based on performing a combinatorial operation between two given configurations. Combinatorial structures such as lattices, affine and projective planes are considered as the constituent configurations. Using this method, we present several classes of well-structured four-cycle free LDPC codes of high rates most of which are quasi-cyclic. From among the main advantages of this approach, we may refer to its low-complexity property and the fact that from performance perspective the constructed codes compete with the pseudorandom LDPC codes.

A source ={s1, s2, …} having a binary Huffman code with code-word lengths satisfying l1=1, l2=2, … is called an anti-uniform source. If l1=1, l2=2, … , li=i, then the source is called an i-level partially anti-uniform source. The redundancy, expected codeword length and entropy of anti-uniform sources are dealt here. A tight upper bound is derived for the expected codeword length L of anti-uniform sources. It is shown that L does not exceed $\surd{5}+3/2$. For each $1\lt L\le \lpar \surd{5}+3\rpar /2$, an anti-uniform distribution achieving maximum entropy H(P)max=L log L−(L−1)log(L−1) is introduced. This shows that the maximum entropy achieved by anti-uniform distributions does not exceed 2.512. It is shown that the range of redundancy values for i-level partially anti-uniform sources with distribution {pi} is an interval of length ∑j=i+1pj. This results in a realistic approximation for the redundancy of these sources.

The problem of selecting a code for finite monotone sources with N symbols is considered. The selection criterion is based on minimizing the average redundancy (called Minave criterion) instead of its maximum (i.e., Minimax criterion). The average probability distribution PNmacr, whose associated Huffman code has the minimum average redundancy, is derived. The entropy of the average distribution (i.e., H(PNmacr)) and the average entropy of the monotone distributions (i.e., H(PNmacr)) are studied. It is shown that both logN-H(PNmacr) and logN-H(PNmacr) are asymptotically equal to a constant (sime0.61). Therefore, there is only a negligible penalty (at most 1.61 bits/symbol) in using a simple fixed-length code with respect to the optimal code. An efficient near-optimal encoding technique is also proposed. The consequences of the two approaches, i.e., Minave and Minimax, are compared in terms of their associated distributions and associated codes. In order to evaluate the average performance of the Minimax code, we prove that the informational divergence of the average distribution and Minimax distribution asymptotically grows as -2.275+loglogN

In decoding a linear block code C by iterative decoding algorithms, these algorithms are essentially applied on a graphical representation of C such as Tanner graph and factor graph. Due to the impact of the structure of these graphs on the performance of code, we consider minimal parity check matrices(matrices with minimum number of nonzero entries) of product codes. An algorithm constructing such matrices is given. It turns out that under the given construction method, product coding technique is indeed a powerful method to construct irregular LDPC codes. Given two codes A and B, the construction method produces a Tanner graph with girth g := min {8, ga, gb} for the product code A ⊗ B, where ga and gb are the girth of Tanner graphs representing A and B, respectively. Simulation results confirm the positive practical impact of the minimality of the parity check matrices.

A source S = {s1, s2, ...} having a binary Huffman code with codeword lengths satisfying l1= 1, l2= 2, ...(and ln-1= ln = n - 1 when |S| = n) is called an antiuniform source. If l1= 1, l2= 2, ..., li = i, then the source is called an i-level partially antiuniform source. In this paper the redundancy, the expected codeword lengths, and the entropy of partially antiuniform sources is studied. It is shown that the range of the redundancy R of a given i-level partially antiuniform source with distribution {pi} is an interval of length pi+1 + ... +pn. This results in a realistic approximation for R. An upper bound is derived for the expected codeword lengths L of antiuniform sources. It is shown that L is less than three. The entropy H of any antiuniform source with average codeword lengths L is bounded above by LlogL - (L - 1) log(L - 1) and hence it does not exceed 2.76.

The minimax distribution PFNdefined by the probabilities pi,FN= 1/lambdaN(i-1)(i-1)/iiplays an important role in the context of encoding finite monotone sources with unknown probabilities. The Shannon code for this distribution is a suboptimal minimax code. The average performance of this suboptimal code is considered in this paper. In order to evaluate the average performance of the minimax code, we compare it with the minave code which minimizes the average redundancy over all monotone sources with N symbols. To achieve this, we study the informational divergence of the minave and minimax distributions and prove that it asymptotically grows as -2.275+log log N. The log log N degradation in average performance should not be regarded as a drawback of the minimax code because the minimum average codeword length over the class of monotone sources grows as log N, which asymptotically dominates log log N

Let E/sub m/ denote the binary (m, m-1, 2) even weight code and /spl ominus/ the Kronecker product operation. A linear code of length m/spl times/t containing E/sub m//spl ominus/(t,1,t) can be decoded efficiently using a Tanner graph and a trellis diagram together with the Wagner decoding algorithm. Thus, it is important to determine whether a given code contains such a subcode. We show that the (18,9,6) binary quadratic residue code does not contain E/sub 6//spl ominus/(3,1,3). The maximum minimum distance of such a code is 5.

We present a method for maximum likelihood decoding of the (48,24,12) quadratic residue code. This method is based on projecting the code onto a subcode with an acyclic Tanner graph, and representing the set of coset leaders by a trellis diagram. This results in a two level coset decoding which can be considered a systematic generalization of the Wagner rule. We show that unlike the (24,12,8) Golay code, the (48,24,12) code does not have a Pless-construction which has been an open question in the literature. It is determined that the highest minimum distance of a (48,24) binary code having a Pless (1986) construction is 10, and up to equivalence there are three such codes.

Given a quasi-cyclic code with minimum Hamming distance d, a set of convolutional codes is derived with free distance equal to d. It is shown that an increase in the rate of these codes results in a decrease in the memory length. The connection between these codes is illustrated with several well-known quasi-cyclic codes. The free distance of some partial unit memory convolutional codes can be determined using the results in this correspondence.

The largest quasi-cyclic subcode of the Reed-Muller code R(r,m), invariant under the shift T/sup 2m-l/ is determined. This code, denoted QCR(r,m,l), is presented through its module decomposition into cyclic submodules. The smallest regular trellis diagram (SRTD) is defined for block codes. This trellis and its construction algorithm are given for the class of cyclic-form codes. Using the cyclic-form structure of QCR(r,m,l), the 2/sup l/-section SRTD of this code is determined. The eight-section SRTD is given for the Reed-Muller codes R(r,m). The quasi-cyclic subcodes of R(r,m) with regular 2/sup l/-section minimal trellis diagrams are presented.