Открытый доступ
Доступ предоставлен
Только для подписчиков
Том 54, № 4 (2018)
- Год: 2018
- Статей: 5
- URL: https://journal-vniispk.ru/0032-9460/issue/view/10153
Coding Theory
Polar Codes with Higher-Order Memory
Аннотация
We introduce a construction of a set of code sequences {Cn(m) : n ≥ 1, m ≥ 1} with memory order m and code length N(n). {Cn(m)} is a generalization of polar codes presented by Arıkan in [1], where the encoder mapping with length N(n) is obtained recursively from the encoder mappings with lengths N(n − 1) and N(n − m), and {Cn(m)} coincides with the original polar codes when m = 1. We show that {Cn(m)} achieves the symmetric capacity I(W) of an arbitrary binary-input, discrete-output memoryless channel W for any fixed m. We also obtain an upper bound on the probability of block-decoding error Pe of {Cn(m)} and show that \({P_e} = O({2^{ - {N^\beta }}})\) is achievable for β < 1/[1+m(ϕ − 1)], where ϕ ∈ (1, 2] is the largest real root of the polynomial F(m, ρ) = ρm − ρm − 1 − 1. The encoding and decoding complexities of {Cn(m)} decrease with increasing m, which proves the existence of new polar coding schemes that have lower complexity than Arıkan’s construction.
301-328
Refinements of Levenshtein Bounds in q-ary Hamming Spaces
Аннотация
We develop refinements of the Levenshtein bound in q-ary Hamming spaces by taking into account the discrete nature of the distances versus the continuous behavior of certain parameters used by Levenshtein. We investigate the first relevant cases and present new bounds. In particular, we derive generalizations and q-ary analogs of the MacEliece bound. Furthermore, we provide evidence that our approach is as good as the complete linear programming and discuss how faster are our calculations. Finally, we present a table with parameters of codes which, if exist, would attain our bounds.
329-342
On the Complexity of Fibonacci Coding
Аннотация
We show that converting an n-digit number from a binary to Fibonacci representation and backward can be realized by Boolean circuits of complexity O(M(n) log n), where M(n) is the complexity of integer multiplication. For a more general case of r-Fibonacci representations, the obtained complexity estimates are of the form \({2^O}{(\sqrt {\log n} )_n}\).
343-350
Methods of Signal Processing
Noise Level Estimation in High-Dimensional Linear Models
Аннотация
We consider the problem of estimating the noise level σ2 in a Gaussian linear model Y = Xβ+σξ, where ξ ∈ ℝn is a standard discrete white Gaussian noise and β ∈ ℝp an unknown nuisance vector. It is assumed that X is a known ill-conditioned n × p matrix with n ≥ p and with large dimension p. In this situation the vector β is estimated with the help of spectral regularization of the maximum likelihood estimate, and the noise level estimate is computed with the help of adaptive (i.e., data-driven) normalization of the quadratic prediction error. For this estimate, we compute its concentration rate around the pseudo-estimate ||Y − Xβ||2/n.
351-371
Large Systems
Exponentially Ramsey Sets
Аннотация
We study chromatic numbers of spaces \(\mathbb{R}_p^n=(\mathbb{R}^n, \ell_p)\) with forbidden monochromatic sets. For some sets, we for the first time obtain explicit exponentially growing lower bounds for the corresponding chromatic numbers; for some others, we substantially improve previously known bounds.
372-396