284 results
Search Results
102. Subspace Codes Based on Graph Matchings, Ferrers Diagrams, and Pending Blocks.
- Author
-
Silberstein, Natalia and Trautmann, Anna-Lena
- Subjects
SUBSPACES (Mathematics) ,LINEAR network coding ,WIRELESS sensor networks ,INFORMATION theory - Abstract
This paper provides new constructions and lower bounds for subspace codes, using Ferrers diagram rank-metric codes from matchings of the complete graph and pending blocks. We present different constructions for constant dimension codes with minimum injection distance 2 or $k-1$ , where $k$ is the constant dimension. Furthermore, we present a construction of new codes from old codes for any minimum distance. Then, we construct nonconstant dimension codes from these codes. Some examples of codes obtained by these constructions are the largest known codes for the given parameters. [ABSTRACT FROM PUBLISHER]
- Published
- 2015
- Full Text
- View/download PDF
103. Convolutional Codes in Rank Metric With Application to Random Network Coding.
- Author
-
Wachter-Zeh, Antonia, Stinner, Markus, and Sidorenko, Vladimir
- Subjects
LINEAR network coding ,DECODING algorithms ,NETWORK performance ,ERROR correction (Information theory) ,ERROR-correcting codes - Abstract
Random network coding recently attracts attention as a technique to disseminate information in a network. This paper considers a noncoherent multishot network, where the unknown and time-variant network is used several times. In order to create dependence between the different shots, particular convolutional codes in rank metric are used. These codes are so-called (partial) unit memory ((P)UM) codes, i.e., convolutional codes with memory one. First, distance measures for convolutional codes in rank metric are shown and two constructions of (P)UM codes in rank metric based on the generator matrices of maximum rank distance codes are presented. Second, an efficient error-erasure decoding algorithm for these codes is presented. Its guaranteed decoding radius is derived and its complexity is bounded. Finally, it is shown how to apply these codes for error correction in random linear and affine network coding. [ABSTRACT FROM AUTHOR]
- Published
- 2015
- Full Text
- View/download PDF
104. Encoding and Indexing of Lattice Codes.
- Author
-
Kurkoski, Brian M.
- Subjects
LATTICE theory ,INDEXING ,ENCODING ,MATRICES (Mathematics) ,DIOPHANTINE equations - Abstract
Encoding and indexing of lattice codes is generalized from self-similar lattice codes to a broader class of lattices. If coding lattice $\Lambda_{\mathrm c}$ and shaping lattice $\Lambda_{\mathrm s}$ satisfy $\Lambda _{\mathrm s}\subseteq \Lambda _{\mathrm c}$ , then $\Lambda _{\mathrm c}/ \Lambda _{\mathrm s}$ is a quotient group that can be used to form a (nested) lattice code $\mathcal C$. Conway and Sloane’s method of encoding and indexing does not apply when the lattices are not self-similar. Results are provided for two classes of lattices. 1) If $\Lambda _{\mathrm c}$ and $\Lambda _{\mathrm s}$ both have generator matrices in a triangular form that satisfies $\Lambda _{\mathrm s}\subseteq \Lambda _{\mathrm c}$ , then encoding is always possible. 2) When $\Lambda _{\mathrm c}$ and $\Lambda _{\mathrm s}$ are described by full generator matrices, if a solution to a linear diophantine equation exists, then encoding is possible. In addition, special cases where $\mathcal C$ is a cyclic code are considered. A condition for the existence of a group isomorphism between the information and $\mathcal C$ is given. The results are applicable to a variety of coding lattices, including Construction A, Construction D, and low-density lattice codes. A variety of shaping lattices may be used as well, including convolutional code lattices and the direct sum of important lattices such as $D_{4}$ , $E_{8}$ , etc. Thus, a lattice code $\mathcal C$ can be designed by selecting $\Lambda _{\mathrm c}$ and $\Lambda _{\mathrm s}$ separately, avoiding the competing design requirements of self-similar lattice codes. [ABSTRACT FROM AUTHOR]
- Published
- 2018
- Full Text
- View/download PDF
105. Quantum Synchronizable Codes From Finite Geometries.
- Author
-
Fujiwara, Yuichiro and Vandendriessche, Peter
- Subjects
FINITE geometries ,ERROR-correcting codes ,QUANTUM noise ,LINEAR codes ,ERROR correction (Information theory) - Abstract
Quantum synchronizable error-correcting codes are special quantum error-correcting codes that are designed to correct both the effect of quantum noise on qubits and misalignment in block synchronization. It is known that, in principle, such a code can be constructed through a combination of a classical linear code and its subcode if the two are both cyclic and dual-containing. However, finding such classical codes that lead to promising quantum synchronizable error-correcting codes is not a trivial task. In fact, although there are two families of classical codes that are proved to produce quantum synchronizable codes with good minimum distances and highest possible tolerance against misalignment, their code lengths have been restricted to primes and Mersenne numbers. In this paper, examining the incidence vectors of projective spaces over the finite fields of characteristic 2, we give quantum synchronizable codes from cyclic codes whose lengths are not primes or Mersenne numbers. These projective geometric codes achieve good performance in quantum error correction and possess the best possible ability to recover synchronization, thereby enriching the variety of good quantum synchronizable codes. We also extend the current knowledge of cyclic codes in classical coding theory by explicitly giving generator polynomials of the finite geometric codes and completely characterizing the minimum weight nonzero codewords. In addition to the codes based on projective spaces, we carry out a similar analysis on the well-known cyclic codes from Euclidean spaces that are known to be majority logic decodable and determine their exact minimum distances. [ABSTRACT FROM PUBLISHER]
- Published
- 2014
- Full Text
- View/download PDF
106. A Coding-Theoretic Application of Baranyai’s Theorem.
- Author
-
Zhang, Liang Feng
- Subjects
HYPERGRAPHS ,HADAMARD codes ,CODING theory ,EXPONENTS ,COMBINATORICS - Abstract
Baranyai’s theorem is well known in the theory of hypergraphs. A corollary of this theorem says that one can partition the family of all \(u\) -subsets of an \(n\) -element set into \({n-1\choose u-1}\) subfamilies such that each subfamily forms a partition of the \(n\) -element set, where \(n\) is divisible by \(u\) . In this paper, we present a coding-theoretic application of Baranyai’s theorem. More precisely, we propose a combinatorial construction of locally decodable codes. Locally decodable codes are error-correcting codes that allow the recovery of any message symbol by looking at only a few symbols of the codeword. The number of looked codeword symbols is called query complexity. Such codes have attracted a lot of attention in recent years. The Walsh–Hadamard code is a well-known binary two-query locally decodable code of exponential length that can recover any message bit using 2 bits of the codeword. Our construction can give locally decodable codes over small finite fields for any constant query complexities. In particular, it gives a ternary two-query locally decodable code of length asymptotically shorter than the Walsh–Hadamard code. [ABSTRACT FROM PUBLISHER]
- Published
- 2014
- Full Text
- View/download PDF
107. Irregular MDS Array Codes.
- Author
-
Tosato, Filippo and Sandell, Magnus
- Subjects
WIRELESS sensor networks ,RESOURCE management ,REDUNDANCY in engineering ,LOW density parity check codes ,INFORMATION retrieval ,BLOCK codes - Abstract
In this paper, we extend the concept of maximum-distance separable (MDS) array codes to a larger class of codes, where the array columns contain a variable number of data and parity symbols and the codewords cannot be arranged, in general, in a regular array structure with equal column length. These new codes, named irregular MDS array codes, find applications in problems of distributed data storage with multiple sources of information generating data at unequal rates. We solve the problem of finding optimal parity symbol allocations that achieve minimum redundancy for a given level of protection against block erasures. We provide a classification of irregular MDS array codes according to the parameters of their parity symbol allocation and we show how regular MDS array codes are a special case of this wider class. We derive necessary and sufficient conditions for such irregular array codes to be MDS and extend the concept of the lowest density generator matrix. Finally, we show how a simple constructive method allows to design irregular lowest density MDS array codes with alphabet size independent of the size of the array columns. [ABSTRACT FROM AUTHOR]
- Published
- 2014
- Full Text
- View/download PDF
108. Batched Sparse Codes.
- Author
-
Yang, Shenghao and Yeung, Raymond W.
- Subjects
NEURAL codes ,ROUTING (Computer network management) ,DATA transmission systems ,LINEAR network coding ,INFORMATION retrieval ,COMPUTATIONAL complexity ,ENCODING - Abstract
Network coding can significantly improve the transmission rate of communication networks with packet loss compared with routing. However, using network coding usually incurs high computational and storage costs in the network devices and terminals. For example, some network coding schemes require the computational and/or storage capacities of an intermediate network node to increase linearly with the number of packets for transmission, making such schemes difficult to be implemented in a router-like device that has only constant computational and storage capacities. In this paper, we introduce batched sparse code (BATS code), which enables a digital fountain approach to resolve the above issue. BATS code is a coding scheme that consists of an outer code and inner code. The outer code is a matrix generation of a fountain code. It works with the inner code that comprises random linear coding at the intermediate network nodes. BATS codes preserve such desirable properties of fountain codes as ratelessness and low encoding/decoding complexity. The computational and storage capacities of the intermediate network nodes required for applying BATS codes are independent of the number of packets for transmission. Almost capacity-achieving BATS code schemes are devised for unicast networks and certain multicast networks. For general multicast networks, under different optimization criteria, guaranteed decoding rates for the destination nodes can be obtained. [ABSTRACT FROM AUTHOR]
- Published
- 2014
- Full Text
- View/download PDF
109. All Binary Linear Codes That Are Invariant Under ${\mathrm{PSL}}_2(n)$.
- Author
-
Ding, Cunsheng, Liu, Hao, and Tonchev, Vladimir D.
- Subjects
LINEAR codes ,CYCLIC codes ,BLOCK codes ,RESIDUE codes ,INFORMATION theory - Abstract
The projective special linear group ${\mathrm {PSL}}_{2}(n)$ is 2-transitive for all primes $n$ and 3-homogeneous for $n \equiv 3 \pmod {4}$ on the set $\{0,1, \ldots, n-1, \infty \}$. It is known that the extended odd-like quadratic residue codes are invariant under ${\mathrm {PSL}}_{2}(n)$. Hence, the extended quadratic residue codes hold an infinite family of 2-designs for primes $n \equiv 1 \pmod {4}$ , an infinite family of 3-designs for primes $n \equiv 3 \pmod {4}$. To construct more $t$ -designs with $t \in \{2, 3\}$ , one would search for other extended cyclic codes over finite fields that are invariant under the action of ${\mathrm {PSL}}_{2}(n)$. The objective of this paper is to prove that the extended quadratic residue binary codes are the only nontrivial extended binary cyclic codes that are invariant under ${\mathrm {PSL}}_{2}(n)$. [ABSTRACT FROM AUTHOR]
- Published
- 2018
- Full Text
- View/download PDF
110. Constacyclic Symbol-Pair Codes: Lower Bounds and Optimal Constructions.
- Author
-
Chen, Bocong, Lin, Liren, and Liu, Hongwei
- Subjects
CYCLIC codes ,HAMMING distance ,METRIC spaces ,DISCRETE Fourier transforms ,FINITE fields - Abstract
Symbol-pair codes introduced by Cassuto and Blaum (2010) are designed to protect against pair errors in symbol-pair read channels. The higher the minimum pair distance, the more pair errors the code can correct. Maximum distance separable (MDS) symbol-pair codes are optimal in the sense that pair distance cannot be improved for given length and code size. The contribution of this paper is twofold. First, we present three lower bounds for the minimum pair distance of constacyclic codes, the first two of which generalize the previously known results due to Cassuto and Blaum (2011) and Kai et al. (2015). The third one exhibits a lower bound for the minimum pair distance of repeated-root cyclic codes. Second, we obtain new MDS symbol-pair codes with minimum pair distance seven and eight through repeated-root cyclic codes. [ABSTRACT FROM AUTHOR]
- Published
- 2017
- Full Text
- View/download PDF
111. Lattice Codes for the Wiretap Gaussian Channel: Construction and Analysis.
- Author
-
Oggier, Frederique, Sole, Patrick, and Belfiore, Jean-Claude
- Subjects
GAUSSIAN channels ,WIRETAPPING ,LATTICE constants ,LATTICE gauge theories ,LATTICE models (Statistical physics) - Abstract
We consider the Gaussian wiretap channel, where two legitimate players Alice and Bob communicate over an additive white Gaussian noise (AWGN) channel, while Eve is eavesdropping, also through an AWGN channel. We propose a coding strategy based on lattice coset encoding. We define the secrecy gain as a design criterion for wiretap lattice codes, expressed in terms of the lattice theta series, which characterizes Eve’s confusion as a function of the channel parameters. The secrecy gain is studied for even unimodular lattices, and an asymptotic analysis shows that it grows exponentially in the dimension of the lattice. Examples of wiretap lattice codes are given. [ABSTRACT FROM AUTHOR]
- Published
- 2016
- Full Text
- View/download PDF
112. Classification of Binary Self-Dual Codes of Length 40.
- Author
-
Bouyukliev, Iliya, Dzhumalieva-Stoeva, Maria, and Monev, Venelin
- Subjects
ISOMORPHISM (Mathematics) ,GROUP theory ,HADAMARD matrices ,HADAMARD codes ,REED-Muller codes - Abstract
An efficient isomorph-free generation algorithm for classification of binary self-dual codes with the minimum distance $d = 4$ is presented. It is combined with another isomorph-free generation algorithm for classification of self-dual codes with the minimum distance $d \ge 6$ . A complete classification of all binary self-dual codes of length 40 is given as a result. [ABSTRACT FROM PUBLISHER]
- Published
- 2015
- Full Text
- View/download PDF
113. Extremal Type I \mathbb Zk -Codes and $k$ -Frames of Odd Unimodular Lattices.
- Author
-
Harada, Masaaki
- Subjects
MODULAR lattices ,VECTORS (Calculus) ,INFORMATION theory ,INTEGERS ,CODING theory - Abstract
For some extremal (optimal) odd unimodular lattice L in dimensions 12, 16, 20, 28, 32, 36, 40, and 44, we determine all integers k such that L contains a k -code of lengths 12, 16, 20, 32, 36, 40, and 44, and a near-extremal Type I \mathbb {Z}_{k} -code of length 28 for positive integers k$ with only a few exceptions. [ABSTRACT FROM PUBLISHER]
- Published
- 2015
- Full Text
- View/download PDF
114. Constructing Linear Encoders With Good Spectra.
- Author
-
Yang, Shengtian, Honold, Thomas, Chen, Yan, Zhang, Zhaoyang, and Qiu, Peiliang
- Subjects
LINEAR codes ,CODING theory ,LOW density parity check codes ,INFORMATION theory ,PROBABILITY theory - Abstract
Linear encoders with good joint spectra are suitable candidates for optimal lossless joint source-channel coding (JSCC), where the joint spectrum is a variant of the input–output complete weight distribution and is considered good if it is close to the average joint spectrum of all linear encoders (of the same coding rate). In spite of their existence, little is known on how to construct such encoders in practice. This paper is devoted to their construction. In particular, two families of linear encoders are presented and proved to have good joint spectra. The first family is derived from Gabidulin codes, a class of maximum-rank-distance codes. The second family is constructed using a serial concatenation of an encoder of a low-density parity-check code (as outer encoder) with a low-density generator matrix encoder (as inner encoder). In addition, criteria for good linear encoders are defined for three coding applications: 1) lossless source coding; 2) channel coding; and 3) lossless JSCC. In the framework of the code-spectrum approach, these three scenarios correspond to the problems of constructing linear encoders with good kernel spectra, good image spectra, and good joint spectra, respectively. Good joint spectra imply both good kernel spectra and good image spectra, and for every linear encoder having a good kernel (respectively, image) spectrum, it is proved that there exists a linear encoder not only with the same kernel (respectively, image) but also with a good joint spectrum. Thus, a good joint spectrum is the most important feature of a linear encoder. [ABSTRACT FROM AUTHOR]
- Published
- 2014
- Full Text
- View/download PDF
115. Channel Code Using Constrained-Random-Number Generator Revisited.
- Author
-
Muramatsu, Jun and Miyake, Shigeki
- Subjects
CIPHERS ,DECODING algorithms ,ENCODING ,INFORMATION & communication technologies ,ARCHITECTURE - Abstract
A construction of a channel code by using a source code with decoder side information is introduced. The encoder and decoder pair of any source code can be used for the construction. Constrained-random-number generators, which generate random numbers satisfying a condition specified by a function and its value, are used to construct stochastic encoders and decoders. The result suggests that we can divide the channel coding problem into the problems of channel encoding and source decoding with side information. [ABSTRACT FROM AUTHOR]
- Published
- 2019
- Full Text
- View/download PDF
116. Binary Images of${\mathbb{Z}_2\mathbb{Z}_4}$-Additive Cyclic Codes.
- Author
-
Borges, Joaquim, Dougherty, Steven T., Fernandez-Cordoba, Cristina, and Ten-Valls, Roger
- Subjects
BINARY codes ,ALGEBRAIC codes ,LINEAR codes ,CYCLIC codes ,POLYNOMIALS ,NUMBER theory - Abstract
A ${\mathbb {Z}}_{2}{\mathbb {Z}}_{4}$ -additive code ${\mathcal{ C}}\subseteq {\mathbb {Z}}_{2}^\alpha \times {\mathbb {Z}}_{4}^\beta $ is called cyclic if the set of coordinates can be partitioned into two subsets, the set of ${\mathbb {Z}}_{2}$ and the set of ${\mathbb {Z}}_{4}$ coordinates, such that any cyclic shift of the coordinates of both subsets leaves the code invariant. We study the binary images of $\mathbb {Z}_{2} \mathbb {Z}_{4} $ -additive cyclic codes. We determine all ${\mathbb {Z}_{2}\mathbb {Z}_{4}}$ -additive cyclic codes with odd $\beta $ whose Gray images are linear binary codes. In this case, it is shown that such binary codes are permutation equivalent (by the Nechaev permutation) to $\mathbb {Z}_{2}$ -double cyclic codes. Finally, the generator polynomials of these binary codes are given. [ABSTRACT FROM AUTHOR]
- Published
- 2018
- Full Text
- View/download PDF
117. On the Symbol-Pair Distance of Repeated-Root Constacyclic Codes of Prime Power Lengths.
- Author
-
Dinh, Hai Q., Nguyen, Bac Trong, Singh, Abhay Kumar, and Sriboonchitta, Songsak
- Subjects
CODING theory ,FINITE fields ,DIGITAL signal processing ,ERROR correction (Information theory) ,MDS (Computer system) - Abstract
Let p be a prime, and \lambda be a nonzero element of the finite field \mathbb Fp^{m} . The \lambda -constacyclic codes of length p^s over \mathbb Fp^{m} are linearly ordered under set-theoretic inclusion, i.e., they are the ideals \langle (x-\lambda 0)^{i} \rangle , 0 \leq i \leq p^s of the chain ring [(\mathbb Fp^{m[x]})/({\langle x^{p^{s}}-\lambda \rangle })] . This structure is used to establish the symbol-pair distances of all such $\lambda$ -constacyclic codes. Among others, all maximum distance separable symbol-pair constacyclic codes of length p^s are obtained. [ABSTRACT FROM AUTHOR]
- Published
- 2018
- Full Text
- View/download PDF
118. The Capacity of Private Information Retrieval From Coded Databases.
- Author
-
Banawan, Karim and Ulukus, Sennur
- Subjects
INFORMATION retrieval ,DATABASES ,COMPUTER science ,LINEAR codes ,ELECTRONIC data processing - Abstract
We consider the problem of private information retrieval (PIR) over a distributed storage system. The storage system consists of N non-colluding databases, each storing an MDS-coded version of M messages. In the PIR problem, the user wishes to retrieve one of the available messages without revealing the message identity to any individual database. We derive the information-theoretic capacity of this problem, which is defined as the maximum number of bits of the desired message that can be privately retrieved per one bit of downloaded information. We show that the PIR capacity in this case is C=(1+K/N+K^2/N^2+\cdots +K^M-1/N^M-1)^-1=(1+Rc+Rc^2+\cdots +Rc^M-1)^-1=({1-Rc})/({1-Rc^{M}}) , where Rc is the rate of the $(N,K)$ MDS code used. The capacity is a function of the code rate and the number of messages only regardless of the explicit structure of the storage code. The result implies a fundamental tradeoff between the optimal retrieval cost and the storage cost when the storage code is restricted to the class of MDS codes. The result generalizes the achievability and converse results for the classical PIR with replicated databases to the case of MDS-coded databases. [ABSTRACT FROM PUBLISHER]
- Published
- 2018
- Full Text
- View/download PDF
119. Capacity-Achieving Rate-Compatible Polar Codes.
- Author
-
Hong, Song-Nam, Hui, Dennis, and Maric, Ivana
- Subjects
CODING theory ,DECODERS (Electronics) ,CHANNEL capacity (Telecommunications) ,AUTOMATIC Repeat reQuest (Data transmission system) ,ARBITRARY constants - Abstract
A method of constructing rate-compatible polar codes that are capacity achieving at multiple code rates with low-complexity sequential decoders is presented. The underlying idea of the construction exploits certain common characteristics of polar codes that are optimized for a sequence of successively degraded channels. The proposed code consists of parallel concatenation of multiple polar codes with information-bit divider at the input of each polar encoder. Thus, it is referred to as parallel concatenated polar (PCP) codes. A lower-rate PCP code is simply constructed by adding more constituent polar codes, which enables incremental retransmissions at different rates in order to adapt to channel conditions. Due to the length limitation of polar codes, the PCP code can only support a restricted set of rates that is characterized by the size of the kernel when conventional polar codes are used. To overcome this limitation, punctured polar codes, which provide more flexibility on blocklength by controlling a puncturing fraction, are considered as constituent codes. The existence of capacity-achieving punctured polar codes for any given puncturing fraction is proven. Using such punctured polar codes as constituent codes, it is shown that the proposed PCP code is capacity achieving for an arbitrary sequence of rates and for any class of degraded channels. [ABSTRACT FROM AUTHOR]
- Published
- 2017
- Full Text
- View/download PDF
120. Coset Construction for Subspace Codes.
- Author
-
Heinlein, Daniel and Kurz, Sascha
- Subjects
SUBSPACES (Mathematics) ,LINEAR network coding ,ALGEBRAIC codes ,GAUSSIAN elimination ,GEOMETRICAL constructions - Abstract
One of the main problems of the research area of network coding is to compute good lower and upper bounds of the achievable cardinality of so-called subspace codes in \mathcal Pq(n) , i.e., the set of subspaces of \mathbb Fq^{n} , for a given minimal distance. Here we generalize a construction of Etzion and Silberstein to a wide range of parameters. This construction, named coset construction, improves or attains several of the previously best-known subspace code sizes and attains the maximum-rank distance bound for an infinite family of parameters. [ABSTRACT FROM AUTHOR]
- Published
- 2017
- Full Text
- View/download PDF
121. Characterization of Metrics Induced by Hierarchical Posets.
- Author
-
Machado, Roberto Assis, Pinheiro, Jerry Anderson, and Firer, Marcelo
- Subjects
- *
PARTIALLY ordered sets , *LINEAR codes , *CHEBYSHEV approximation , *MATHEMATICAL decomposition , *GENERATORS (Computer programs) - Abstract
In this paper, we consider metrics determined by hierarchical posets and give explicit formulas for the main parameters of a linear code: the minimum distance and the packing, covering, and Chebyshev radii of a code. We also present ten characterizations of hierarchical poset metrics, including new characterizations and simple new proofs to the known ones. [ABSTRACT FROM AUTHOR]
- Published
- 2017
- Full Text
- View/download PDF
122. On Subsets of the Normal Rational Curve.
- Author
-
Ball, Simeon and De Beule, Jan
- Subjects
- *
BOREL subsets , *DIMENSIONAL analysis , *CONIC sections , *LINEAR codes , *REED-Solomon codes - Abstract
A normal rational curve of the (k-1) -dimensional projective space over {\mathbb F}_{q} is an arc of size q+1$ , since any k$ points of the curve span the whole space. In this paper, we will prove that if q$ is odd, then a subset of size 3k-6$ of a normal rational curve cannot be extended to an arc of size q+2$ . In fact, we prove something slightly stronger. Suppose that q$ is odd and E$ is a (2k-3)$ -subset of an arc G$ of size 3k-6$ . If G$ projects to a subset of a conic from every (k-3)$ -subset of E of odd characteristic, which can be extended to a Reed–Solomon code of length $q+1$ , cannot be extended to a linear maximum distance separable code of length $q+2$ . [ABSTRACT FROM AUTHOR]
- Published
- 2017
- Full Text
- View/download PDF
123. Sparse Quantum Codes From Quantum Circuits.
- Author
-
Bacon, Dave, Flammia, Steven T., Harrow, Aram W., and Shi, Jonathan
- Subjects
QUANTUM computing ,ERROR-correcting codes ,QUBITS ,ERROR correction (Information theory) ,CONSTRAINTS (Physics) - Abstract
We describe a general method for turning quantum circuits into sparse quantum subsystem codes. The idea is to turn each circuit element into a set of low-weight gauge generators that enforce the input–output relations of that circuit element. Using this prescription, we can map an arbitrary stabilizer code into a new subsystem code with the same distance and number of encoded qubits but where all the generators have constant weight, at the cost of adding some ancilla qubits. With an additional overhead of ancilla qubits, the new code can also be made spatially local. Applying our construction to certain concatenated stabilizer codes yields families of subsystem codes with constant-weight generators and with minimum distance d = n^1- \epsilon , where \epsilon = O(1/\sqrt \log n) . For spatially local codes in D dimensions, we nearly saturate a bound due to Bravyi and Terhal and achieve d = n^{1- \epsilon -1/D} . Previously the best code distance achievable with constant-weight generators in any dimension, due to Freedman, Meyer, and Luo, was O(\sqrt {n\log n})$ for a stabilizer code. [ABSTRACT FROM PUBLISHER]
- Published
- 2017
- Full Text
- View/download PDF
124. \mathbb Z2\mathbb Z4 -Additive Cyclic Codes, Generator Polynomials, and Dual Codes.
- Author
-
Borges, Joaquim, Fernandez-Cordoba, Cristina, and Ten-Valls, Roger
- Subjects
CYCLIC codes ,POLYNOMIALS ,DUAL codes (Coding theory) ,SET theory ,GENERATORS of groups - Abstract
A \mathbb Z2\mathbb Z4 -additive code \mathcal C\subseteq \mathbb Z2^\alpha \times \mathbb Z4^\beta is called cyclic if the set of coordinates can be partitioned into two subsets, the set of \mathbb Z2 and the set of \mathbb Z4 coordinates, such that any cyclic shift of the coordinates of both subsets leaves the code invariant. These codes can be identified as submodules of the \mathbb Z4[x] -module \mathbb Z2[x]/(x^\alpha -1)\times \mathbb Z4[x]/(x^\beta -1) . The parameters of a \mathbb Z2\mathbb Z4 -additive cyclic code are stated in terms of the degrees of the generator polynomials of the code. The generator polynomials of the dual code of a \mathbb Z2\mathbb Z4 -additive cyclic code are determined in terms of the generator polynomials of the code \mathcal C . [ABSTRACT FROM PUBLISHER]
- Published
- 2016
- Full Text
- View/download PDF
125. Self-Orthogonality Matrix and Reed-Muller Codes.
- Author
-
Kim, Jon-Lark and Choi, Whan-Hyuk
- Subjects
REED-Muller codes ,TWO-dimensional bar codes ,LINEAR codes ,BINARY codes ,EDIBLE fats & oils - Abstract
Kim et al. (2021) gave a method to embed a given binary $[n,k]$ code $\mathcal {C}\,\,(k = 3, 4)$ into a self-orthogonal code of the shortest length which has the same dimension $k$ and minimum distance $d' \ge d(\mathcal {C})$. We extend this result by proposing a new method related to a special matrix, called the self-orthogonality matrix $SO_{k}$ , obtained by shortening a Reed-Muller code ${\mathcal R}(2,k)$. Using this approach, we can extend binary linear codes to many optimal self-orthogonal codes of dimensions 5 and 6. Furthermore, we partially disprove the conjecture (Kim et al. (2021)) by showing that if $31 \le n \le 256$ and $n\equiv 14,22,29 \pmod {31}$ , then there exist optimal $[n], [5]$ codes which are self-orthogonal. We also construct optimal self-orthogonal $[n], [6]$ codes when $41 \le n \le 256$ satisfies $n \ne 46, 54, 61$ and $n \equiv \!\!\!\!\!/~7, 14, 22, 29, 38, 45, 53, 60 \pmod {63}$. [ABSTRACT FROM AUTHOR]
- Published
- 2022
- Full Text
- View/download PDF
126. Provable Compressed Sensing With Generative Priors via Langevin Dynamics.
- Author
-
Nguyen, Thanh V., Jagatap, Gauri, and Hegde, Chinmay
- Subjects
COMPRESSED sensing ,INVERSE problems ,PERFORMANCE standards ,ORTHOGONAL matching pursuit ,HEURISTIC algorithms ,STOCHASTIC processes - Abstract
Deep generative models have emerged as a powerful class of priors for signals in various inverse problems such as compressed sensing, phase retrieval and super-resolution. In this work, we consider the compressed sensing problem and assume the unknown signal to lie in the range of some pre-trained generative model. A popular approach for signal recovery is via gradient descent in the low-dimensional latent space. While gradient descent has achieved good empirical performance, its theoretical behavior is not well understood. We introduce the use of stochastic gradient Langevin dynamics (SGLD) for compressed sensing with a generative prior. Under mild assumptions on the generative model, we prove the convergence of SGLD to the true signal. We also demonstrate competitive empirical performance to standard gradient descent. [ABSTRACT FROM AUTHOR]
- Published
- 2022
- Full Text
- View/download PDF
127. Quantum Pin Codes.
- Author
-
Vuillot, Christophe and Breuckmann, Nikolas P.
- Subjects
REED-Muller codes ,COLOR codes ,QUANTUM computing ,LOGIC circuits - Abstract
We introduce quantum pin codes: a class of quantum CSS codes. Quantum pin codes are a generalization of quantum color codes and Reed-Muller codes and share a lot of their structure and properties. Pin codes have gauge operators, an unfolding procedure and their stabilizers form so-called $\ell $ -orthogonal spaces meaning that the joint overlap between any $\ell $ stabilizer elements is always even. This last feature makes them interesting for devising magic-state distillation protocols, for instance by using puncturing techniques. We study examples of these codes and their properties. [ABSTRACT FROM AUTHOR]
- Published
- 2022
- Full Text
- View/download PDF
128. More Efficient Privacy Amplification With Less Random Seeds via Dual Universal Hash Function.
- Author
-
Hayashi, Masahito and Tsurumaru, Toyohiro
- Subjects
RANDOM access memory ,AMPLIFICATION reactions ,COMPUTATIONAL complexity ,QUANTUM cryptography ,ENTROPY (Information theory) - Abstract
We explicitly construct random hash functions for privacy amplification (extractors) that require smaller random seed lengths than the previous literature, and still allow efficient implementations with complexity $O(n\log n)$ for input length $n$ . The key idea is the concept of dual universal2 hash function introduced recently. We also use a new method for constructing extractors by concatenating $\delta $ -almost dual universal2 hash functions with other extractors. Besides minimizing seed lengths, we also introduce methods that allow one to use non-uniform random seeds for extractors. These methods can be applied to a wide class of extractors, including dual universal2 hash function, as well as to the conventional universal2 hash functions. [ABSTRACT FROM AUTHOR]
- Published
- 2016
- Full Text
- View/download PDF
129. Optimal Families of Perfect Polyphase Sequences From the Array Structure of Fermat-Quotient Sequences.
- Author
-
Park, Ki-Hyeon, Song, Hong-Yeop, Kim, Dae San, and Golomb, Solomon W.
- Subjects
MULTIPHASE flow ,TIME series analysis ,STOCHASTIC processes ,AUTOCORRELATION (Statistics) ,MOBILE communication systems - Abstract
We show that a p -ary polyphase sequence of period p^{2} from the Fermat quotients is perfect. That is, its periodic autocorrelation is zero for all non-trivial phase shifts. We call this Fermat-quotient sequence. We propose a collection of optimal families of perfect polyphase sequences using the Fermat-quotient sequences in the sense of the Sarwate bound. That is, the cross correlation of two members in a family is upper bounded by p . To investigate some relation between Fermat-quotient sequences and Frank-Zadoff sequences and to construct optimal families including these sequences, we introduce generators of p -ary polyphase sequences of period p^{2} using their p\times p$ array structures. We call an optimal generator to be the generator of some $p$ -ary polyphase sequences which are perfect and which gives an optimal family by the proposed construction. Finally, we propose an algebraic construction for optimal generators as another main result. A lot of optimal families of size $p-1$ can be constructed from these optimal generators, some of which are known to be from the Fermat-quotient sequences or from the Frank-Zadoff sequences, but some families are new for $p\geq 11$ . The relation between the Fermat-quotient sequences and the Frank-Zadoff sequences is determined as a by-product. [ABSTRACT FROM AUTHOR]
- Published
- 2016
- Full Text
- View/download PDF
130. A Class of Two-Weight and Three-Weight Codes and Their Applications in Secret Sharing.
- Author
-
Ding, Kelan and Ding, Cunsheng
- Subjects
- *
LINEAR codes , *DISTRIBUTION (Probability theory) , *HAMMING weight , *FINITE fields , *GAUSSIAN distribution , *GAUSSIAN sums , *CODING theory - Abstract
In this paper, a class of two-weight and three-weight linear codes over \mathrm GF(p) is constructed, and their application in secret sharing is investigated. Some of the linear codes obtained are optimal in the sense that they meet certain bounds on linear codes. These codes have applications also in authentication codes, association schemes, and strongly regular graphs, in addition to their applications in consumer electronics, communication and data storage systems. [ABSTRACT FROM PUBLISHER]
- Published
- 2015
- Full Text
- View/download PDF
131. Critical Pairs for the Product Singleton Bound.
- Author
-
Mirandola, Diego and Zemor, Gilles
- Subjects
SINGLETON bounds ,CODING theory ,REED-Solomon codes ,ERROR-correcting codes ,CRYPTOGRAPHY ,LINEAR codes - Abstract
We characterize product-maximum distance separable (PMDS) pairs of linear codes, i.e., pairs of codes $C$ and $D$ whose product under coordinatewise multiplication has maximum possible minimum distance as a function of the code length and the dimensions $\dim C$ and $\dim D$ . We prove in particular, for $C=D$ , that if the square of the code $C$ has minimum distance at least 2, and $(C,C)$ is a PMDS pair, then either $C$ is a generalized Reed–Solomon code, or $C$ is a direct sum of self-dual codes. In passing we establish coding-theory analogues of classical theorems of additive combinatorics. [ABSTRACT FROM AUTHOR]
- Published
- 2015
- Full Text
- View/download PDF
132. Convolutional Codes With a Maximum Distance Profile Based on Skew Polynomials.
- Subjects
CODECS - Abstract
We construct a family of $(n,k)$ convolutional codes with degree $\delta \in \{k,n-k\}$ that have a maximum distance profile. The field size required for our construction is $\Theta (n^{2\delta })$ , which improves upon the known constructions of convolutional codes with a maximum distance profile. Our construction is based on the theory of skew polynomials. [ABSTRACT FROM AUTHOR]
- Published
- 2022
- Full Text
- View/download PDF
133. Optimal Locally Repairable Codes: An Improved Bound and Constructions.
- Author
-
Cai, Han, Fan, Cuiling, Miao, Ying, Schwartz, Moshe, and Tang, Xiaohu
- Subjects
HAMMING distance ,LINEAR codes - Abstract
We study the Singleton-type bound that provides an upper limit on the minimum distance of locally repairable codes. We present an improved bound by carefully analyzing the combinatorial structure of the repair sets. Thus, we show the previous bound is unachievable for certain parameters. We then also provide explicit constructions of optimal codes which show that for certain parameters the new bound is sharp. Additionally, as a byproduct, some previously known codes are shown to attain the new bound and are thus proved to be optimal. [ABSTRACT FROM AUTHOR]
- Published
- 2022
- Full Text
- View/download PDF
134. On the Generalized Covering Radii of Reed-Muller Codes.
- Author
-
Elimelech, Dor, Wei, Hengjia, and Schwartz, Moshe
- Subjects
REED-Muller codes ,LINEAR codes ,RADIUS (Geometry) ,HAMMING weight ,EXTREME value theory ,POINT set theory - Abstract
We study generalized covering radii, a fundamental property of linear codes that characterizes the trade-off between storage, latency, and access in linear data-query protocols such as PIR. We prove lower and upper bounds on the generalized covering radii of Reed-Muller codes, as well as finding their exact value in certain extreme cases. With the application to linear data-query protocols in mind, we also construct a covering algorithm that gets as input a set of points in space, and find a corresponding set of codewords from the Reed-Muller code that are jointly not farther away from the input than the upper bound on the generalized covering radius of the code. We prove that the algorithm runs in time that is polynomial in the code parameters. [ABSTRACT FROM AUTHOR]
- Published
- 2022
- Full Text
- View/download PDF
135. Block Markov Superposition Transmission: Construction of Big Convolutional Codes From Short Codes.
- Author
-
Ma, Xiao, Liang, Chulong, Huang, Kechao, and Zhuang, Qiutao
- Subjects
SUPERPOSITION principle (Physics) ,SIGNAL convolution ,MARKOV processes ,MULTIUSER channels ,BIT error rate - Abstract
A construction of big convolutional codes from short codes called block Markov superposition transmission (BMST) is proposed. The BMST is very similar to superposition block Markov encoding (SBME), which has been widely used to prove multiuser coding theorems. The BMST codes can also be viewed as a class of spatially coupled codes, where the generator matrices of the involved short codes (referred to as basic codes) are coupled. The encoding process of BMST can be as fast as that of the basic code, while the decoding process can be implemented as an iterative sliding-window decoding algorithm with a tunable delay. More importantly, the performance of BMST can be simply lower bounded in terms of the transmission memory given that the performance of the short code is available. Numerical results show that: 1) the lower bounds can be matched with a moderate decoding delay in the low bit-error-rate (BER) region, implying that the iterative sliding-window decoding algorithm is near optimal; 2) BMST with repetition codes and single parity-check codes can approach the Shannon limit within 0.5 dB at the BER of 10^-5 for a wide range of code rates; and 3) BMST can also be applied to nonlinear codes. [ABSTRACT FROM AUTHOR]
- Published
- 2015
- Full Text
- View/download PDF
136. Construction A of Lattices Over Number Fields and Block Fading (Wiretap) Coding.
- Author
-
Kositwattanarerk, Wittawat, Ong, Soon Sheng, and Oggier, Frederique
- Subjects
LATTICE constants ,CYCLOTOMIC fields ,BINARY codes ,RADIO transmitter fading ,WIRETAPPING - Abstract
We propose a lattice construction from totally real and complex multiplication fields, which naturally generalizes Construction A of lattices from p -ary codes obtained from the cyclotomic field \mathbb {Q}(\zeta _{p}) , p a prime, which in turn contains the so-called Construction A of lattices from binary codes as a particular case. We focus on the maximal totally real subfield \mathbb Q(\zeta p^{r}\,+\,\zeta p^{-r}) of the cyclotomic field \mathbb Q(\zeta p^{r}) , $r\geq 1$ . Our construction has applications to coset encoding of algebraic lattice codes for block fading channels, and in particular for block fading wiretap channels. [ABSTRACT FROM AUTHOR]
- Published
- 2015
- Full Text
- View/download PDF
137. Squares of Random Linear Codes.
- Author
-
Cascudo, Ignacio, Cramer, Ronald, Mirandola, Diego, and Zemor, Gilles
- Subjects
LINEAR codes ,QUADRATIC forms ,GENERATORS (Computer programs) ,ERROR-correcting codes ,RANDOM codes (Coding theory) - Abstract
Given a linear code $C$ , one can define the d$ th power of C$ as the span of all componentwise products of d$ elements of C$ . A power of C or smaller. Moreover, the convergence speed is exponential if the difference $k(k+1)/2-n$ is at least linear in $k$ . The proof uses random coding and combinatorial arguments, together with algebraic tools involving the precise computation of the number of quadratic forms of a given rank, and the number of their zeros. [ABSTRACT FROM PUBLISHER]
- Published
- 2015
- Full Text
- View/download PDF
138. Interference Networks With no CSIT: Impact of Topology.
- Author
-
Naderializadeh, Navid and Avestimehr, Amir Salman
- Subjects
INTERFERENCE (Telecommunication) ,TRANSMITTERS (Communication) ,LINEAR algebra ,GRAPH theory ,BENCHMARKING (Management) ,WIRELESS communications - Abstract
We consider partially connected $K$ -user interference networks, where the transmitters have no knowledge about the channel gain values, but they are aware of network topology. We introduce several linear algebraic and graph theoretic concepts to derive new topology-based outer bounds and inner bounds on the symmetric degrees-of-freedom of these networks. We evaluate our bounds for two classes of networks to demonstrate their tightness for most networks in these classes, quantify the gain of our inner bounds over benchmark interference management strategies, and illustrate the effect of network topology on these gains. [ABSTRACT FROM AUTHOR]
- Published
- 2015
- Full Text
- View/download PDF
139. Repair Locality With Multiple Erasure Tolerance.
- Author
-
Wang, Anyu and Zhang, Zhifang
- Subjects
FORWARD error correction ,MATHEMATICAL bounds ,INPUT-output analysis ,COORDINATES ,CODING theory - Abstract
In distributed storage systems, erasure codes with locality \(r\) are preferred because a coordinate can be locally repaired by accessing at most \(r\) other coordinates which in turn greatly reduces the disk I/O complexity for small \(r\) . However, the local repair may not be performed when some of the \(r\) coordinates are also erased. To overcome this problem, we propose the \((r,\delta )_{c}\) -locality providing \(\delta -1\) nonoverlapping local repair groups of size no more than \(r\) for a coordinate. Consequently, the repair locality \(r\) can tolerate \(\delta -1\) erasures in total. We derive an upper bound on the minimum distance for any linear \([n,k]\) code with information \((r,\delta )_{c}\) -locality. Then, we prove existence of the codes that attain this bound when \(n\geq k(r(\delta -1)+1)\) . Although the locality \((r,\delta )\) defined by Prakash et al. provides the same level of locality and local repair tolerance as our definition, codes with \((r,\delta )_{c}\) -locality attaining the bound are proved to have more advantage in the minimum distance. In particular, we construct a class of codes with all symbol \((r,\delta )_{c}\) -locality where the gain in minimum distance is \(\Omega (\sqrt {r})\) and the information rate is close to 1. [ABSTRACT FROM PUBLISHER]
- Published
- 2014
- Full Text
- View/download PDF
140. Sequences With High Nonlinear Complexity.
- Author
-
Niederreiter, Harald and Xing, Chaoping
- Subjects
COMPUTATIONAL complexity ,NONLINEAR systems ,FINITE fields ,COMPUTER simulation ,RANDOM numbers ,CRYPTOGRAPHY - Abstract
We improve lower bounds on the \(k\) th-order nonlinear complexity of pseudorandom sequences over finite fields, including explicit inversive sequences and sequences obtained from Hermitian function fields, and we establish a probabilistic result on the behavior of the \(k\) th-order nonlinear complexity of random sequences over finite fields. [ABSTRACT FROM AUTHOR]
- Published
- 2014
- Full Text
- View/download PDF
141. On the Security of Subspace Subcodes of Reed–Solomon Codes for Public Key Encryption.
- Author
-
Couvreur, Alain and Lequesne, Matthieu
- Subjects
REED-Solomon codes ,POLYNOMIAL time algorithms ,PUBLIC key cryptography - Abstract
This article discusses the security of McEliece-like encryption schemes using subspace subcodes of Reed–Solomon codes, i.e. subcodes of Reed–Solomon codes over ${\mathbb {F}_{q^{m}}}$ whose entries lie in a fixed collection of ${\mathbb {F}_{q}}$ –subspaces of ${\mathbb {F}_{q^{m}}}$. These codes appear to be a natural generalisation of Goppa and alternant codes and provide a broader flexibility in designing code based encryption schemes. For the security analysis, we introduce a new operation on codes called the twisted product which yields a polynomial time distinguisher on such subspace subcodes as soon as the chosen ${\mathbb {F}_{q}}$ –subspaces have dimension larger than $m/2$. From this distinguisher, we build an efficient attack which in particular breaks some parameters of a recent proposal due to Khathuria, Rosenthal and Weger. [ABSTRACT FROM AUTHOR]
- Published
- 2022
- Full Text
- View/download PDF
142. Computer Classification of Linear Codes.
- Author
-
Bouyukliev, Iliya, Bouyuklieva, Stefka, and Kurz, Sascha
- Subjects
LINEAR codes ,FINITE fields ,CLASSIFICATION algorithms ,CLASSIFICATION ,COMPUTERS - Abstract
Two algorithms for the classification of linear codes over finite fields are presented. One of the algorithms is based on canonical augmentation and the other one on lattice point enumeration. New classification results over fields with 2, 3 and 4 elements are obtained. [ABSTRACT FROM AUTHOR]
- Published
- 2021
- Full Text
- View/download PDF
143. The Geometry of Two-Weight Codes Over ℤ p m.
- Author
-
Shi, Minjia, Honold, Thomas, Sole, Patrick, Qiu, Yunzhen, Wu, Rongsheng, and Sepasdar, Zahra
- Subjects
REGULAR graphs ,PROJECTIVE geometry ,LINEAR codes ,GRAPH theory ,GEOMETRY ,TWO-dimensional bar codes ,CODE generators - Abstract
We investigate fat projective linear codes over ${\mathbb Z}_{p^{m}}$ , $m\geqslant 2$ , with two nonzero homogeneous weights (“two-weight codes”), building on the graph theory approach developed by Delsarte for codes over fields. Our main result is the classification of such codes under the additional assumption that the columns of a generator matrix of the code determine a cap in the projective Hjelmslev geometry $\mathop {\mathrm {PHG}}\nolimits (k-1, {\mathbb Z}_{p^{m}})$. This generalizes a result on projective two weight codes with dual distance at least four (Calderbank, 1982). The proof relies on a careful analysis of a certain strongly regular graph built on the cosets of the dual code, and on an interpretation of its parameters in terms of projective Hjelmslev geometry. [ABSTRACT FROM AUTHOR]
- Published
- 2021
- Full Text
- View/download PDF
144. Systematic Security Analysis of Stream Encryption With Key Erasure.
- Author
-
Chen, Yu Long, Luykx, Atul, Mennink, Bart, and Preneel, Bart
- Subjects
STREAM ciphers ,BLOCK ciphers ,PERMUTATIONS - Abstract
We consider a generalized construction of stream ciphers with forward security. The design framework is modular: it is built from a so-called layer function that updates the key and (optionally) the nonce and generates a new pseudorandom output stream. We analyze the generalized construction for four different instantiations: two possible layer functions that are in turn instantiated with either a block cipher or a pseudorandom function. We prove that each of these instantiations gives a stream cipher that is pseudorandom and forward secure in the multi-user setting with a very tight bound. A comprehensive analysis shows that the two block cipher based instantiations achieve very similar bounds. For the pseudorandom function based instantiations there is no clear winner: either layer can be beneficial over the other one, depending on the choice of parameters. By instantiating the pseudorandom function with a generic construction such as the sum of permutations, we obtain a highly efficient and competitive stream cipher based on an n-bit block cipher that is secure beyond the $2^{\text {n}/2}$ birthday bound. [ABSTRACT FROM AUTHOR]
- Published
- 2021
- Full Text
- View/download PDF
145. New Constructions of Optimal Locally Repairable Codes With Super-Linear Length.
- Author
-
Kong, Xiangliang, Wang, Xin, and Ge, Gennian
- Subjects
PARITY-check matrix ,HYPERGRAPHS ,LINEAR codes ,SPARSE matrices - Abstract
As an important coding scheme in modern distributed storage systems, locally repairable codes (LRCs) have attracted a lot of attentions from perspectives of both practical applications and theoretical research. As a major topic in the research of LRCs, bounds and constructions of the corresponding optimal codes are of particular concerns. In this work, codes with $(r,\delta)$ -locality which have optimal minimal distance w.r.t. the bound given by Prakash et al. are considered. Through parity-check matrix approach, constructions of both optimal $(r,\delta)$ -LRCs with all symbol locality ($(r,\delta)_{a}$ -LRCs) and optimal $(r,\delta)$ -LRCs with information locality ($(r,\delta)_{i}$ -LRCs) are provided. As a generalization of a work of Xing and Yuan, these constructions are built on a connection between sparse hypergraphs and optimal $(r,\delta)$ -LRCs. With the help of constructions of large sparse hypergraphs, the lengths of codes obtained from our construction can be super-linear in the alphabet size. This improves upon previous constructions when the minimal distance of the code is at least $3\delta +1$. As two applications, optimal H-LRCs with super-linear lengths and GSD codes with unbounded lengths are also constructed. [ABSTRACT FROM AUTHOR]
- Published
- 2021
- Full Text
- View/download PDF
146. On Communication for Distributed Babai Point Computation.
- Author
-
Bollauf, Maiara F., Vaishampayan, Vinay A., and Costa, Sueli I. R.
- Subjects
ERROR probability ,DISTRIBUTED computing ,DISTRIBUTED algorithms ,DATA compression ,RANDOM graphs - Abstract
We present a communication-efficient distributed protocol for computing the Babai point, an approximate nearest point for a random vector ${\mathbf{X}}\in \mathbb {R}^{n}$ in a given lattice. We show that the protocol is optimal in the sense that it minimizes the sum rate when the components of $\boldsymbol {X}$ are mutually independent. We then investigate the error probability, i.e. the probability that the Babai point does not coincide with the nearest lattice point, motivated by the fact that for some cases, a distributed algorithm for finding the Babai point is sufficient for finding the nearest lattice point itself. Two different probability models for $\boldsymbol {X}$ are considered—uniform and Gaussian. For the uniform model, in dimensions two and three, the error probability is seen to grow with the packing density, and we demonstrate that the densest lattice in dimension two presents the worst error probability. For higher dimensions, we develop probabilistic concentration bounds as well as bounds based on geometric arguments for the error probability. The probabilistic bounds lead to the conclusion that for lattices which generate suitably thin coverings of $\mathbb {R}^{n}$ (which includes lattices that meet Rogers’ bound on the covering radius), the error probability goes to unity as $n$ grows. Probabilistic and geometric bounds are also used to estimate the error probability under the uniform model for various lattices including the $A_{n}$ family and the Leech lattice, $\Lambda _{24}$. On the other hand, for the Gaussian model, the error probability goes to zero as the lattice dimension tends to infinity, provided the noise variance is sufficiently small. [ABSTRACT FROM AUTHOR]
- Published
- 2021
- Full Text
- View/download PDF
147. A Comparison of Distance Bounds for Quasi-Twisted Codes.
- Author
-
Ezerman, Martianus Frederic, Lampos, John Mark, Ling, San, Ozkaya, Buket, and Tharnnukhroh, Jareena
- Subjects
CODING theory ,SPECTRAL theory ,EIGENVALUES ,POLYNOMIALS ,FINITE fields ,PRODUCT coding - Abstract
Spectral bounds on the minimum distance of quasi-twisted codes over finite fields are proposed, based on eigenvalues of polynomial matrices and the corresponding eigenspaces. They generalize the Semenov-Trifonov and Zeh-Ling bounds in a way similar to how the Roos and shift bounds extend the BCH and HT bounds for cyclic codes. The eigencodes of a quasi-twisted code in the spectral theory and the outer codes in its concatenated structure are related. A comparison based on this relation verifies that the Jensen bound always outperforms the spectral bound under special conditions, which yields a similar relation between the Lally and the spectral bounds. The performances of the Lally, Jensen and spectral bounds are presented in comparison with each other. [ABSTRACT FROM AUTHOR]
- Published
- 2021
- Full Text
- View/download PDF
148. Further Results on the Relative Generalized Hamming Weight.
- Author
-
Liu, Zihui and Wei, Yao
- Subjects
HAMMING weight - Abstract
Based on the applications to the wire-tap channel and bounds on the relative generalized Hamming weight, we will introduce optimal codes of type $\mathcal {I}$ and type $\mathcal {II}$. We will give some necessary conditions and the explicit construction for a linear code $\mathcal {C}$ to be optimal of type $\mathcal {I}$ and $\mathcal {II}$ with respect to a subcode $\mathcal {C}_{1}$. We will also present a new bound on two different parameters of the relative generalized Hamming weight. [ABSTRACT FROM AUTHOR]
- Published
- 2021
- Full Text
- View/download PDF
149. Sum-Rank BCH Codes and Cyclic-Skew-Cyclic Codes.
- Subjects
NONCOMMUTATIVE rings ,FINITE rings ,ABSTRACT algebra ,REED-Solomon codes ,TWO-dimensional bar codes - Abstract
In this work, cyclic-skew-cyclic codes and sum-rank BCH codes are introduced. Cyclic-skew-cyclic codes are characterized as left ideals of a suitable non-commutative finite ring, constructed using skew polynomials on top of polynomials (or vice versa). Single generators of such left ideals are found, and they are used to construct generator matrices of the corresponding codes. The notion of defining set is introduced, using pairs of roots of skew polynomials on top of poynomials. A lower bound (called sum-rank BCH bound) on the minimum sum-rank distance is given for cyclic-skew-cyclic codes whose defining set contains certain consecutive pairs. Sum-rank BCH codes, with prescribed minimum sum-rank distance, are then defined as the largest cyclic-skew-cyclic codes whose defining set contains such consecutive pairs. The defining set of a sum-rank BCH code is described, and a lower bound on its dimension is obtained. Thanks to it, tables are provided showing that sum-rank BCH codes beat previously known codes for the sum-rank metric for binary $2 \times 2 $ matrices (i.e., codes whose codewords are lists of $2 \times 2 $ binary matrices, for a wide range of list lengths that correspond to the code length). Finally, a decoder for sum-rank BCH codes up to half their prescribed distance is obtained. [ABSTRACT FROM AUTHOR]
- Published
- 2021
- Full Text
- View/download PDF
150. Efficient Approximate Minimum Entropy Coupling of Multiple Probability Distributions.
- Subjects
DISTRIBUTION (Probability theory) ,ENTROPY (Information theory) ,RANDOM variables ,RANDOM numbers ,CAUSAL inference - Abstract
Given a collection of probability distributions p
1 , . . . , pm , the minimum entropy coupling is the coupling X1 , . . . , Xm (Xi ∼ pi ) with the smallest entropy H(X1 , . . . , Xm ). While this problem is known to be NP-hard, we present an efficient algorithm for computing a coupling with entropy within 2 bits from the optimal value. More precisely, we construct a coupling with entropy within 2 bits from the entropy of the greatest lower bound of p1 , . . . , pm with respect to majorization. This construction is also valid when the collection of distributions is infinite, and when the supports of the distributions are infinite. Potential applications of our results include random number generation, entropic causal inference, and functional representation of random variables. [ABSTRACT FROM AUTHOR]- Published
- 2021
- Full Text
- View/download PDF
Discovery Service for Jio Institute Digital Library
For full access to our library's resources, please sign in.