The Experts below are selected from a list of 2190 Experts worldwide ranked by ideXlab platform
Chaoping Xing - One of the best experts on this subject based on the ideXlab platform.
-
Asymptotic Gilbert–Varshamov Bound on Frequency Hopping Sequences
IEEE Transactions on Information Theory, 2020Co-Authors: Xianhua Niu, Chaoping Xing, Chen YuanAbstract:Given a ${q}$ -ary frequency hopping sequence set of length ${n}$ and size ${M}$ with Hamming correlation ${H}$ , one can obtain a ${q}$ -ary (nonlinear) cyclic code of length ${n}$ and size nM with Hamming distance n-H . Thus, every upper Bound on the size of a code from coding theory gives an upper Bound on the size of a frequency hopping sequence set. Indeed, all upper Bounds from coding theory have been converted to upper Bounds on frequency hopping sequence sets [1] . On the other hand, a lower Bound from coding theory does not automatically produce a lower Bound for frequency hopping sequence sets. In particular, the most important lower Bound, the Gilbert-Varshamov Bound in coding theory, has not been transformed to a valid lower Bound on frequency hopping sequence sets. The purpose of this paper is to transform the Gilbert-Varshamov Bound from coding theory to frequency hopping sequence sets by establishing a connection between a special family of cyclic codes (which are called hopping cyclic codes in this paper) and frequency hopping sequence sets. We provide two proofs of the Gilbert-Varshamov Bound. One is based on a probabilistic method that requires advanced tool–martingale. This proof covers the whole rate region. Another proof is purely elementary but only covers part of the rate region.
-
List Decodability of Symbol-Pair Codes
IEEE Transactions on Information Theory, 2019Co-Authors: Shu Liu, Chaoping Xing, Chen YuanAbstract:We investigate the list decodability of symbol-pair codes 1 in this paper. First, we show that the list decodability of every symbol-pair code does not exceed the Gilbert–Varshamov Bound. On the other hand, we are able to prove that with high probability, a random symbol-pair code can be list decoded up to the Gilbert–Varshamov Bound. Our second result of this paper is to derive the Johnson-type Bound, i.e., a lower Bound on list decoding radius in terms of minimum distance. Finally, we present a list decoding algorithm of Reed–Solomon codes beyond the Johnson-type Bound in the pair metric. 1 A symbol-pair code is referred to a code in the pair metric.
-
Asymptotic Gilbert-Varshamov Bound on Frequency Hopping.
arXiv: Information Theory, 2018Co-Authors: Xianhua Niu, Chaoping Xing, Chen YuanAbstract:Given a $q$-ary frequency hopping sequence set of length $n$ and size $M$ with Hamming correlation $H$, one can obtain a $q$-ary (nonlinear) cyclic code of length $n$ and size $nM$ with Hamming distance $n-H$. Thus, every upper Bound on the size of a code from coding theory gives an upper Bound on the size of a frequency hopping sequence set. Indeed, all upper Bounds from coding theory have been converted to upper Bounds on frequency hopping sequence sets (\cite{Ding09}). On the other hand, a lower Bound from coding theory does not automatically produce a lower Bound for frequency hopping sequence sets. In particular, the most important lower Bound--the Gilbert-Varshamov Bound in coding theory has not been transformed to frequency hopping sequence sets. The purpose of this paper is to convert the Gilbert-Varshamov Bound in coding theory to frequency hopping sequence sets by establishing a connection between a special family of cyclic codes (which are called hopping cyclic codes in this paper) and frequency hopping sequence sets. We provide two proofs of the Gilbert-Varshamov Bound. One is based on probabilistic method that requires advanced tool--martingale. This proof covers the whole rate region. The other proof is purely elementary but only covers part of the rate region.
-
Asymptotic Gilbert-Varshamov Bound on Frequency Hopping Sequences.
arXiv: Information Theory, 2018Co-Authors: Xianhua Niu, Chaoping Xing, Chen YuanAbstract:Given a $q$-ary frequency hopping sequence set of length $n$ and size $M$ with Hamming correlation $H$, one can obtain a $q$-ary (nonlinear) cyclic code of length $n$ and size $nM$ with Hamming distance $n-H$. Thus, every upper Bound on the size of a code from coding theory gives an upper Bound on the size of a frequency hopping sequence set. Indeed, all upper Bounds from coding theory have been converted to upper Bounds on frequency hopping sequence sets (\cite{Ding09}). On the other hand, a lower Bound from coding theory does not automatically produce a lower Bound for frequency hopping sequence sets. In particular, the most important lower Bound--the Gilbert-Varshamov Bound in coding theory has not been transformed to frequency hopping sequence sets. The purpose of this paper is to convert the Gilbert-Varshamov Bound in coding theory to frequency hopping sequence sets by establishing a connection between a special family of cyclic codes (which are called hopping cyclic codes in this paper) and frequency hopping sequence sets. We provide two proofs of the Gilbert-Varshamov Bound. One is based on probabilistic method that requires advanced tool--martingale. This proof covers the whole rate region. The other proof is purely elementary but only covers part of the rate region.
-
List Decodability of Symbol-Pair Codes
2018Co-Authors: Shu Liu, Chaoping Xing, Chen YuanAbstract:We investigate the list decodability of symbol-pair codes in the present paper. Firstly, we show that list decodability of every symbol-pair code does not exceed the Gilbert-Varshamov Bound. On the other hand, we are able to prove that with high probability, a random symbol-pair code can be list decoded up to the Gilbert-Varshamov Bound. Our second result of this paper is to derive the Johnson-type Bound, i.e., a lower Bound on list decoding radius in terms of minimum distance. Finally, we present a list decoding algorithm of Reed-Solomon codes beyond the Johnson-type Bound.
Chen Yuan - One of the best experts on this subject based on the ideXlab platform.
-
Asymptotic Gilbert–Varshamov Bound on Frequency Hopping Sequences
IEEE Transactions on Information Theory, 2020Co-Authors: Xianhua Niu, Chaoping Xing, Chen YuanAbstract:Given a ${q}$ -ary frequency hopping sequence set of length ${n}$ and size ${M}$ with Hamming correlation ${H}$ , one can obtain a ${q}$ -ary (nonlinear) cyclic code of length ${n}$ and size nM with Hamming distance n-H . Thus, every upper Bound on the size of a code from coding theory gives an upper Bound on the size of a frequency hopping sequence set. Indeed, all upper Bounds from coding theory have been converted to upper Bounds on frequency hopping sequence sets [1] . On the other hand, a lower Bound from coding theory does not automatically produce a lower Bound for frequency hopping sequence sets. In particular, the most important lower Bound, the Gilbert-Varshamov Bound in coding theory, has not been transformed to a valid lower Bound on frequency hopping sequence sets. The purpose of this paper is to transform the Gilbert-Varshamov Bound from coding theory to frequency hopping sequence sets by establishing a connection between a special family of cyclic codes (which are called hopping cyclic codes in this paper) and frequency hopping sequence sets. We provide two proofs of the Gilbert-Varshamov Bound. One is based on a probabilistic method that requires advanced tool–martingale. This proof covers the whole rate region. Another proof is purely elementary but only covers part of the rate region.
-
List Decodability of Symbol-Pair Codes
IEEE Transactions on Information Theory, 2019Co-Authors: Shu Liu, Chaoping Xing, Chen YuanAbstract:We investigate the list decodability of symbol-pair codes 1 in this paper. First, we show that the list decodability of every symbol-pair code does not exceed the Gilbert–Varshamov Bound. On the other hand, we are able to prove that with high probability, a random symbol-pair code can be list decoded up to the Gilbert–Varshamov Bound. Our second result of this paper is to derive the Johnson-type Bound, i.e., a lower Bound on list decoding radius in terms of minimum distance. Finally, we present a list decoding algorithm of Reed–Solomon codes beyond the Johnson-type Bound in the pair metric. 1 A symbol-pair code is referred to a code in the pair metric.
-
Asymptotic Gilbert-Varshamov Bound on Frequency Hopping.
arXiv: Information Theory, 2018Co-Authors: Xianhua Niu, Chaoping Xing, Chen YuanAbstract:Given a $q$-ary frequency hopping sequence set of length $n$ and size $M$ with Hamming correlation $H$, one can obtain a $q$-ary (nonlinear) cyclic code of length $n$ and size $nM$ with Hamming distance $n-H$. Thus, every upper Bound on the size of a code from coding theory gives an upper Bound on the size of a frequency hopping sequence set. Indeed, all upper Bounds from coding theory have been converted to upper Bounds on frequency hopping sequence sets (\cite{Ding09}). On the other hand, a lower Bound from coding theory does not automatically produce a lower Bound for frequency hopping sequence sets. In particular, the most important lower Bound--the Gilbert-Varshamov Bound in coding theory has not been transformed to frequency hopping sequence sets. The purpose of this paper is to convert the Gilbert-Varshamov Bound in coding theory to frequency hopping sequence sets by establishing a connection between a special family of cyclic codes (which are called hopping cyclic codes in this paper) and frequency hopping sequence sets. We provide two proofs of the Gilbert-Varshamov Bound. One is based on probabilistic method that requires advanced tool--martingale. This proof covers the whole rate region. The other proof is purely elementary but only covers part of the rate region.
-
Asymptotic Gilbert-Varshamov Bound on Frequency Hopping Sequences.
arXiv: Information Theory, 2018Co-Authors: Xianhua Niu, Chaoping Xing, Chen YuanAbstract:Given a $q$-ary frequency hopping sequence set of length $n$ and size $M$ with Hamming correlation $H$, one can obtain a $q$-ary (nonlinear) cyclic code of length $n$ and size $nM$ with Hamming distance $n-H$. Thus, every upper Bound on the size of a code from coding theory gives an upper Bound on the size of a frequency hopping sequence set. Indeed, all upper Bounds from coding theory have been converted to upper Bounds on frequency hopping sequence sets (\cite{Ding09}). On the other hand, a lower Bound from coding theory does not automatically produce a lower Bound for frequency hopping sequence sets. In particular, the most important lower Bound--the Gilbert-Varshamov Bound in coding theory has not been transformed to frequency hopping sequence sets. The purpose of this paper is to convert the Gilbert-Varshamov Bound in coding theory to frequency hopping sequence sets by establishing a connection between a special family of cyclic codes (which are called hopping cyclic codes in this paper) and frequency hopping sequence sets. We provide two proofs of the Gilbert-Varshamov Bound. One is based on probabilistic method that requires advanced tool--martingale. This proof covers the whole rate region. The other proof is purely elementary but only covers part of the rate region.
-
List Decodability of Symbol-Pair Codes
2018Co-Authors: Shu Liu, Chaoping Xing, Chen YuanAbstract:We investigate the list decodability of symbol-pair codes in the present paper. Firstly, we show that list decodability of every symbol-pair code does not exceed the Gilbert-Varshamov Bound. On the other hand, we are able to prove that with high probability, a random symbol-pair code can be list decoded up to the Gilbert-Varshamov Bound. Our second result of this paper is to derive the Johnson-type Bound, i.e., a lower Bound on list decoding radius in terms of minimum distance. Finally, we present a list decoding algorithm of Reed-Solomon codes beyond the Johnson-type Bound.
Lingfei Jin - One of the best experts on this subject based on the ideXlab platform.
-
On the List-Decodability of Random Self-Orthogonal Codes
arXiv: Information Theory, 2016Co-Authors: Lingfei Jin, Chaoping Xing, Xiande ZhangAbstract:In 2011, Guruswami-H{\aa}stad-Kopparty \cite{Gru} showed that the list-decodability of random linear codes is as good as that of general random codes. In the present paper, we further strengthen the result by showing that the list-decodability of random {\it Euclidean self-orthogonal} codes is as good as that of general random codes as well, i.e., achieves the classical Gilbert-Varshamov Bound. Specifically, we show that, for any fixed finite field $\F_q$, error fraction $\delta\in (0,1-1/q)$ satisfying $1-H_q(\delta)\le \frac12$ and small $\epsilon>0$, with high probability a random Euclidean self-orthogonal code over $\F_q$ of rate $1-H_q(\delta)-\epsilon$ is $(\delta, O(1/\epsilon))$-list-decodable. This generalizes the result of linear codes to Euclidean self-orthogonal codes. In addition, we extend the result to list decoding {\it symplectic dual-containing} codes by showing that the list-decodability of random symplectic dual-containing codes achieves the quantum Gilbert-Varshamov Bound as well. This implies that list-decodability of quantum stabilizer codes can achieve the quantum Gilbert-Varshamov Bound. The counting argument on self-orthogonal codes is an important ingredient to prove our result.
-
A Construction of Permutation Codes From Rational Function Fields and Improvement to the Gilbert–Varshamov Bound
IEEE Transactions on Information Theory, 2016Co-Authors: Lingfei JinAbstract:Due to recent applications to communications over powerlines, multilevel flash memories, and block ciphers, permutation codes have received a lot of attention from both coding and mathematical communities. One of the benchmarks for good permutation codes is the Gilbert–Varshamov Bound. Although there have been several constructions of permutation codes, the Gilbert–Varshamov Bound still remains to be the best asymptotical lower Bound except for a recent improvement in the case of constant minimum distance. In this paper, we present an algebraic construction of permutation codes from rational function fields, and it turns out that, for a prime number $n$ of a symbol length, this class of permutation codes improves the Gilbert–Varshamov Bound by a factor $n$ asymptotically for a minimum distance $d$ with $d=O(\sqrt {n})$ . Furthermore, for a constant minimum distance $d$ , we improve the Gilbert–Varshamov Bound by a factor $n$ as well as the recent one given by Gao et al. by a factor $n/\log n$ asymptotically for all sufficiently large $n$ .
-
On the List-Decodability of Random Self-Orthogonal Codes
IEEE Transactions on Information Theory, 2015Co-Authors: Lingfei Jin, Chaoping Xing, Xiande ZhangAbstract:Guruswami et al. showed that the list-decodability of random linear codes is as good as that of general random codes. In this paper, we further strengthen the result by showing that the list-decodability of random Euclidean self-orthogonal codes is as good as that of general random codes as well, i.e., achieves the classical Gilbert–Varshamov Bound. In particular, we show that, for any fixed finite field $ {\mathbb {F}}_{q}$ , error fraction $\delta \in (0,1-1/q)$ satisfying $1-H_{q}(\delta )\le 1/2$ , and small $\epsilon >0$ , with high probability a random Euclidean self-orthogonal code over $ {\mathbb {F}}_{q}$ of rate $1-H_{q}(\delta )-\epsilon $ is $(\delta ,O(1/\epsilon ))$ -list-decodable. This generalizes the result of linear codes to Euclidean self-orthogonal codes. In addition, we extend the result to list decoding symplectic dual-containing codes by showing that the list-decodability of random symplectic dual-containing codes achieves the quantum Gilbert–Varshamov Bound as well. This implies that list-decodability of quantum stabilizer codes can achieve the quantum Gilbert–Varshamov Bound. The counting argument on self-orthogonal codes is an important ingredient to prove our result.
-
Quantum Gilbert-Varshamov Bound Through Symplectic Self-Orthogonal Codes
arXiv: Information Theory, 2013Co-Authors: Lingfei Jin, Chaoping XingAbstract:It is well known that quantum codes can be constructed through classical symplectic self-orthogonal codes. In this paper, we give a kind of Gilbert-Varshamov Bound for symplectic self-orthogonal codes first and then obtain the Gilbert-Varshamov Bound for quantum codes. The idea of obtaining the Gilbert-Varshamov Bound for symplectic self-orthogonal codes follows from counting arguments.
-
ISIT - Quantum Gilbert-Varshamov Bound through symplectic self-orthogonal codes
2011 IEEE International Symposium on Information Theory Proceedings, 2011Co-Authors: Lingfei Jin, Chaoping XingAbstract:It is well known that quantum codes can be constructed through classical symplectic self-orthogonal codes. In this paper, we give a kind of Gilbert-Varshamov Bound for symplectic self-orthogonal codes first and then obtain the Gilbert-Varshamov Bound for quantum codes. The idea of obtaining the Gilbert-Varshamov Bound for symplectic self-orthogonal codes follows from counting arguments.
Matthew Weidner - One of the best experts on this subject based on the ideXlab platform.
-
Subquadratic Time Encodable Codes Beating the Gilbert–Varshamov Bound
IEEE Transactions on Information Theory, 2019Co-Authors: Anand Kumar Narayanan, Matthew WeidnerAbstract:We construct explicit algebraic geometry codes built from the Garcia–Stichtenoth function-field tower beating the Gilbert–Varshamov Bound for alphabet sizes at least 192. Messages are identified with functions in certain Riemann–Roch spaces associated with divisors supported on multiple places. Encoding amounts to evaluating these functions at degree-one places. By exploiting algebraic structures particular to the Garcia–Stichtenoth tower, we devise an intricate deterministic $\omega /2 runtime exponent encoding and $1+\omega /2 expected runtime exponent randomized (unique and list) decoding algorithms. Here $\omega is the matrix multiplication exponent. If $\omega =2$ , as widely believed, the encoding and decoding runtimes are respectively nearly linear and nearly quadratic. Prior to this work, encoding time of code families beating the Gilbert–Varshamov Bound were quadratic or worse.
-
Nearly linear time encodable codes beating the Gilbert-Varshamov Bound.
arXiv: Information Theory, 2017Co-Authors: Anand Kumar Narayanan, Matthew WeidnerAbstract:We construct explicit nearly linear time encodable error-correcting codes beating the Gilbert-Varshamov Bound. Our codes are algebraic geometry codes built from the Garcia-Stichtenoth function field tower and beat the Gilbert-Varshamov Bound for alphabet sizes at least $19^2$. Messages are identified with functions in certain Riemann-Roch spaces associated with divisors supported on multiple places. Encoding amounts to evaluating these functions at degree one places. By exploiting algebraic structures particular to the Garcia-Stichtenoth tower, we devise an intricate deterministic nearly linear time encoding algorithm and nearly quadratic expected time randomized (unique and list) decoding algorithms.
Yang Ding - One of the best experts on this subject based on the ideXlab platform.
-
On List-Decodability of Random Rank Metric Codes and Subspace Codes
IEEE Transactions on Information Theory, 2015Co-Authors: Yang DingAbstract:Codes in rank metric have a wide range of applications. To construct such codes with better list-decoding performance explicitly, it is of interest to investigate the listdecodability of random rank metric codes. It is shown that if n/m = b is a constant, then for every rank metric code in Fm×n q with rate R and list-decoding radius ρ must obey the Gilbert-Varshamov Bound, that is, R ≤ (1-ρ)(1-bρ). Otherwise, the list size can be exponential and hence no polynomial-time list decoding is possible. On the other hand, for arbitrary 0 0, with E and ρ being independent of each other, with high probability, a random rank metric code with rate R = (1 - ρ)(1 - bρ) - can be efficiently list-decoded up to a fraction ρ of rank errors with constant list size O(1/E). We establish similar results for constant-dimension subspace codes. Moreover, we show that, with high probability, the list-decoding radius of random Fq-linear rank metric codes also achieve the Gilbert-Varshamov Bound with constant list size O(exp(1/E)).