We construct new linear codes with high minimum distance d. In at least 12 cases these codes improve the minimum distance of the previously known best linear codes for fixed parameters n. k. Among these new codes ther...
详细信息
We construct new linear codes with high minimum distance d. In at least 12 cases these codes improve the minimum distance of the previously known best linear codes for fixed parameters n. k. Among these new codes there is an optimal ternary [88, 8. 54](3) code. We develop an algorithm, which starts with already good codes C, i.e. codes with high minimum distance d for given length n and dimension k over the field G F(q). The algorithm is based on the newly defined (l. s)-extension. This is a generalization of the well-known method of adding a parity bit in the case of a binary linear code of odd minimum weight. (I. s)-extension tries to extend the generator matrix of C by adding I columns with the property that at least s of the l letters added to each of the codewords of minimum weight in C are different from 0. If one finds such columns the minimum distance of the extended code is d + s provided that the second smallest weight in C was at least d + s. The question whether such columns exist can be settled using a Diophantine system of equations. (C) 2008 Elsevier B.V. All rights reserved.
In this paper, we provide a generalization of binary quadratic residue codes to the cases of higher power prime residues over the finite field of the same order. We find generating polynomials for Such codes, define a...
详细信息
In this paper, we provide a generalization of binary quadratic residue codes to the cases of higher power prime residues over the finite field of the same order. We find generating polynomials for Such codes, define a new notion corresponding to the binary concept of an idempotent, and use this to find a lower bound for the codeword weight of the duals of such codes. This in turn leads to a lower bound on the weight of the codewords themselves. (C) 2009 Elsevier Inc. All rights reserved.
A family of LDPC codes, called LU(3, q) codes, has been constructed from q-regular bipartite graphs. Recently, P. Sin and Q. Xiang determined the dimensions of these codes in the case that q is a power of an odd prime...
详细信息
A family of LDPC codes, called LU(3, q) codes, has been constructed from q-regular bipartite graphs. Recently, P. Sin and Q. Xiang determined the dimensions of these codes in the case that q is a power of an odd prime. They also obtained a lower bound for the dimension of an LU(3, q) code when q is a power of 2. In this paper we prove that this lower bound is the exact dimension of the LU(3,q) code. The proof involves the geometry of symplectic generalized quadrangles, the representation theory of Sp(4,q), and the ring of polynomials. (C) 2009 Elsevier Inc. All rights reserved.
Packing and covering problems for metric spaces, and graphs in particular, are of essential interest in combinatorics and coding theory. They are formulated in terms of metric balls of vertices. We consider a new prob...
详细信息
Packing and covering problems for metric spaces, and graphs in particular, are of essential interest in combinatorics and coding theory. They are formulated in terms of metric balls of vertices. We consider a new problem in graph theory which is also based on the consideration of metric balls of vertices, but which is distinct from the traditional packing and covering problems. This problem is motivated by applications in information transmission when redundancy of messages is not sufficient for their exact reconstruction, and applications in computational biology when one wishes to restore an evolutionary process. It can be defined as the reconstruction, or identification, of an unknown vertex in a given graph from a minimal number of vertices (erroneous or distorted patterns) in a metric ball of a given radius r around the unknown vertex. For this problem it is required to find minimum restrictions for such a reconstruction to be possible and also to find efficient reconstruction algorithms under such minimal restrictions. In this paper we define error graphs and investigate their basic properties. A particular class of error graphs occurs when the vertices of the graph are the elements of a group, and when the path metric is determined by a suitable set of group elements. These are the undirected Cayley graphs. Of particular interest is the transposition Cayley graph on the symmetric group which occurs in connection with the analysis of transpositional mutations in molecular biology [RA. Pevzner, Computational Molecular Biology: An Algorithmic Approach, MIT Press, Cambridge, MA, 2000;D. Sankoff, N. El-Mabrouk, Genome rearrangement, in: T. Jiang, T. Smith, Y. Xu, M.Q. Zhang (Eds.), Current Topics in Computational Molecular Biology, MIT Press, 2002]. We obtain a complete solution of the above problems for the transposition Cayley graph on the symmetric group. (C) 2008 Published by Elsevier Inc.
Almost difference sets (ADSs) have important applications in cryptography, coding theory, and antenna array thinning. A new approach is proposed to derive ADSs of arbitrary lengths. Such a technique recasts the ADS de...
详细信息
Almost difference sets (ADSs) have important applications in cryptography, coding theory, and antenna array thinning. A new approach is proposed to derive ADSs of arbitrary lengths. Such a technique recasts the ADS design as a combinatorial optimisation problem successively solved by means of a suitable binary genetic algorithm. New ADSs are derived to assess the effectiveness of the proposed approach.
The failures of iterative decoders for low-density parity-check (LDPC) codes on the additive white Gaussian noise channel (AWGNC) and the binary symmetric channel (BSC) can be understood in terms of combinatorial obje...
详细信息
ISBN:
(纸本)9781424458707
The failures of iterative decoders for low-density parity-check (LDPC) codes on the additive white Gaussian noise channel (AWGNC) and the binary symmetric channel (BSC) can be understood in terms of combinatorial objects known as trapping sets. In this paper, we derive a systematic method to identify the most relevant trapping sets for decoding over the BSC in the error floor region. We elaborate on the notion of the critical number of a trapping set and derive a classification of trapping sets. We then develop the trapping set ontology, a database of trapping sets that summarizes the topological relations among trapping sets. We elucidate the usefulness of the trapping set ontology in predicting the error floor as well as in designing better codes.
The design of a good kernel is fundamental for knowledge discovery from graph-structured data. Existing graph kernels exploit only limited information about the graph structures but are still computationally expensive...
详细信息
ISBN:
(纸本)9781424452422
The design of a good kernel is fundamental for knowledge discovery from graph-structured data. Existing graph kernels exploit only limited information about the graph structures but are still computationally expensive. We propose a novel graph kernel based on the structural characteristics of graphs. The key is to represent node labels as binary arrays and characterize each node using logical operations on the label set of the connected nodes. Our kernel has a linear time complexity with respect to the number of nodes times the average number of neighboring nodes in the given graphs. The experimental result shows that the proposed kernel performs comparable and much faster than a state-of-the-art graph kernel for benchmark data sets and shows high scalability for new applications with large graphs.
In order to realize error free communication we have to add appropriate redundancy to the transmitted bit stream. This can be achieved using the Convolutional code. There are a number of techniques for decoding Convol...
详细信息
ISBN:
(纸本)9781424445189
In order to realize error free communication we have to add appropriate redundancy to the transmitted bit stream. This can be achieved using the Convolutional code. There are a number of techniques for decoding Convolutional code. The method used in this work is the Viterbi algorithm which performs maximum likelihood decoding. This work will give an overview to the convolution encoder and the Viterbi decoder. Furthermore, the simulation environment using MATLAB tool in the evaluation of the performance of the decoder with additive white Gaussian noise channel will be considered.
The popular logic puzzle, Sudoku, consists of placing the digits 1,...,9 into a 9 x 9 grid, such that each digit appears only once in each row, column, and subdivided 'mini-grid' of size 3 x 3. Uniqueness of s...
详细信息
ISBN:
(纸本)9789898111661
The popular logic puzzle, Sudoku, consists of placing the digits 1,...,9 into a 9 x 9 grid, such that each digit appears only once in each row, column, and subdivided 'mini-grid' of size 3 x 3. Uniqueness of solution of a puzzle is ensured by the positioning of a number of given values. Quasi-Magic Sudoku adds the further constraint that within each mini-grid, every row, column and diagonal must sum to 15 +/-Delta, where Delta is chosen to take a value between 2 and 8. Recently Sudoku has been shown to have potential for the generation of erasure correction codes. The additional quasi-magic constraint results in far fewer given values being required to ensure uniqueness of solution, raising the prospect of improved usefulness in code generation. Recent work has highlighted useful domain knowledge concerning cell interrelationships in Quasi-Magic Sudoku for the case Delta = 2, providing pruning conditions to reduce the size of search space that need be examined to ensure uniqueness of solution. This paper examines the usefulness of the identified rich knowledge in restricting search space size. The knowledge is implemented as pruning conditions in a backtracking implementation of a Quasi-Magic Sudoku solver, with a further cell ordering heuristic. Analysis of the improvement in processing time, and thereby of the potential usefulness of Quasi-Magic Sudoku for code generation, is provided.
The McEliece-Sidel'nikov cryptosystem is a modification of the McEliece cryptosystem, which is one of the oldest public-key cryptosystems. It was proposed by V. M. Sidel'nikov in 1994 and is based on the u-fol...
详细信息
暂无评论