99 results
Search Results
2. New Constructions of Optimal Cyclic (r, δ) Locally Repairable Codes From Their Zeros.
- Author
-
Qiu, Jing, Zheng, Dabin, and Fu, Fang-Wei
- Subjects
- *
CYCLIC codes , *REED-Solomon codes , *PAPER arts , *GENERALIZATION - Abstract
An $(r, \delta)$ -locally repairable code ($(r, \delta)$ -LRC for short) was introduced by Prakash et al. for tolerating multiple failed nodes in distributed storage systems, which was a generalization of the concept of $r$ -LRCs produced by Gopalan et al.. An $(r, \delta)$ -LRC is said to be optimal if it achieves the Singleton-like bound. Recently, Chen et al. generalized the construction of cyclic $r$ -LRCs proposed by Tamo et al. , and constructed several classes of optimal $(r, \delta)$ -LRCs of length $n$ for $n\, |\, (q-1)$ or $n\,|\, (q+1)$ , respectively in terms of a union of the set of zeros controlling the minimum distance and the set of zeros ensuring the locality. Following the work of , , this paper first characterizes $(r, \delta)$ -locality of a cyclic code via its zeros. Then we construct several classes of optimal cyclic $(r, \delta)$ -LRCs of length $n$ for $n\, |\, (q-1)$ or $n\,|\, (q+1)$ , respectively from the product of two sets of zeros. Our constructions include all optimal cyclic $(r,\delta)$ -LRCs proposed in , , and our method seems more convenient to obtain optimal cyclic $(r, \delta)$ -LRCs with flexible parameters. Moreover, many optimal cyclic $(r,\delta)$ -LRCs of length $n$ for $n\, |\, (q-1)$ or $n\,|\, (q+1)$ , respectively with $(r+\delta -1)\nmid n$ can be obtained from our method. [ABSTRACT FROM AUTHOR]
- Published
- 2021
- Full Text
- View/download PDF
3. Shortened Linear Codes From APN and PN Functions.
- Author
-
Xiang, Can, Tang, Chunming, and Ding, Cunsheng
- Subjects
- *
LINEAR codes , *BINARY codes , *CODING theory , *REED-Muller codes , *GENERATING functions , *NONLINEAR functions - Abstract
Linear codes generated by component functions of perfect nonlinear (PN for short) and almost perfect nonlinear (APN for short) functions and the first-order Reed-Muller codes have been an object of intensive study in coding theory. The objective of this paper is to investigate some binary shortened codes of two families of linear codes from APN functions and some $p$ -ary shortened codes associated with PN functions. The weight distributions of these shortened codes and the parameters of their duals are determined. The parameters of these binary codes and $p$ -ary codes are flexible. Many of the codes presented in this paper are optimal or almost optimal. The results of this paper show that the shortening technique is very promising for constructing good codes. [ABSTRACT FROM AUTHOR]
- Published
- 2022
- Full Text
- View/download PDF
4. The q -Ary Antiprimitive BCH Codes.
- Author
-
Zhu, Hongwei, Shi, Minjia, Wang, Xiaoqiang, and Helleseth, Tor
- Subjects
- *
CYCLIC codes , *LINEAR codes , *DECODING algorithms , *LIQUID crystal displays - Abstract
It is well-known that cyclic codes have efficient encoding and decoding algorithms. In recent years, antiprimitive BCH codes have attracted a lot of attention. The objective of this paper is to study BCH codes of this type over finite fields and analyse their parameters. Some lower bounds on the minimum distance of antiprimitive BCH codes are given. The BCH codes presented in this paper have good parameters in general, containing many optimal linear codes. In particular, two open problems about the minimum distance of BCH codes of this type are partially solved in this paper. [ABSTRACT FROM AUTHOR]
- Published
- 2022
- Full Text
- View/download PDF
5. Binary [ n , (n + 1)/2] Cyclic Codes With Good Minimum Distances.
- Author
-
Tang, Chunming and Ding, Cunsheng
- Subjects
- *
CYCLIC codes , *REED-Muller codes , *BINARY codes , *LINEAR codes - Abstract
The binary quadratic-residue codes and the punctured Reed-Muller codes ${\mathcal {R}}_{2}((m-1)/2, m))$ are two families of binary cyclic codes with parameters $[n, (n+1)/2, d \geq \sqrt {n}]$. These two families of binary cyclic codes are interesting partly due to the fact that their minimum distances have a square-root bound. The objective of this paper is to construct two families of binary cyclic codes of length $2^{m}-1$ and dimension near $2^{m-1}$ with good minimum distances. When $m \geq 3$ is odd, the codes become a family of duadic codes with parameters $[2^{m}-1, 2^{m-1}, d]$ , where $d \geq 2^{(m-1)/2}+1$ if $m \equiv 3 \pmod {4}$ and $d \geq 2^{(m-1)/2}+3$ if $m \equiv 1 \pmod {4}$. The two families of binary cyclic codes contain some optimal binary cyclic codes. [ABSTRACT FROM AUTHOR]
- Published
- 2022
- Full Text
- View/download PDF
6. Geometric Approach to b-Symbol Hamming Weights of Cyclic Codes.
- Author
-
Shi, Minjia, Ozbudak, Ferruh, and Sole, Patrick
- Subjects
- *
CYCLIC codes , *HAMMING weight , *GEOMETRIC approach , *FINITE fields , *BINARY codes , *DECODING algorithms , *HAMMING distance , *ALGEBRAIC curves - Abstract
Symbol-pair codes were introduced by Cassuto and Blaum in 2010 to protect pair errors in symbol-pair read channels. Recently Yaakobi, Bruck and Siegel (2016) generalized this notion to b-symbol codes in order to consider consecutive b errors for a prescribed integer b ≥ 2, and they gave constructions and decoding algorithms. Cyclic codes were considered by various authors as candidates for symbol-pair codes and they established minimum distance bounds on (certain) cyclic codes. In this paper we use algebraic curves over finite fields in order to obtain tight lower and upper bounds on b-symbol Hamming weights of arbitrary cyclic codes over Fq. Here b ≥ 2 is an arbitrary prescribed positive integer and Fq is an arbitrary finite field. We also present a stability theorem for an arbitrary cyclic code C of dimension k and length n: the b-symbol Hamming weight enumerator of C is the same as the k-symbol Hamming weight enumerator of C if k ≤ b ≤ n−1. Moreover, we give improved tight lower and upper bounds on b-symbol Hamming weights of some cyclic codes related to irreducible cyclic codes. Throughout the paper the length n is coprime to q. [ABSTRACT FROM AUTHOR]
- Published
- 2021
- Full Text
- View/download PDF
7. The Subfield Codes and Subfield Subcodes of a Family of MDS Codes.
- Author
-
Tang, Chunming, Wang, Qi, and Ding, Cunsheng
- Subjects
- *
CYCLIC codes , *LIQUID crystal displays , *LINEAR codes - Abstract
Maximum distance separable (MDS) codes are very important in both theory and practice. There is a classical construction of a family of $[{2^{m}+1, 2u-1, 2^{m}-2u+3}]$ MDS codes for $1 \leq u \leq 2^{m-1}$ , which are cyclic, reversible and BCH codes over ${\mathrm {GF}}(2^{m})$. The objective of this paper is to study the quaternary subfield subcodes and quaternary subfield codes of a subfamily of the MDS codes for even $m$. A family of quaternary cyclic codes is obtained. These quaternary codes are distance-optimal in some cases and very good in general. Furthermore, two infinite families of 3-designs from these quaternary codes and their duals are presented. [ABSTRACT FROM AUTHOR]
- Published
- 2022
- Full Text
- View/download PDF
8. The Differential Spectrum of the Power Mapping x p n −3.
- Author
-
Yan, Haode, Xia, Yongbo, Li, Chunlei, Helleseth, Tor, Xiong, Maosheng, and Luo, Jinquan
- Subjects
- *
POWER spectra , *ELLIPTIC curves , *INTEGERS , *WIRELESS communications - Abstract
Let $n$ be a positive integer and $p$ a prime. The power mapping $x^{p^{n}-3}$ over ${\mathbb {F}}_{p^{n}}$ has desirable differential properties, and its differential spectra for $p=2,\,3$ have been determined. In this paper, for any odd prime $p$ , by investigating certain quadratic character sums and some equations over ${\mathbb {F}}_{p^{n}}$ , we determine the differential spectrum of $x^{p^{n}-3}$ with a unified approach. The obtained result shows that for any given odd prime $p$ , the differential spectrum can be expressed explicitly in terms of $n$. Compared with previous results, a special elliptic curve over ${\mathbb {F}}_{p}$ plays an important role in our computation for the general case $p \ge 5$. [ABSTRACT FROM AUTHOR]
- Published
- 2022
- Full Text
- View/download PDF
9. Infection-Probability-Dependent Interlayer Interaction Propagation Processes in Multiplex Networks.
- Author
-
Liu, Juan, Wu, Xiaoqun, Lu, Jinhu, and Wei, Xiang
- Subjects
- *
MULTIPLEXING , *SOCIAL networks - Abstract
Different spreading processes in multiplex networks may interact with each other and display intertwined effects. In this paper, we propose a theoretical framework called infection-probability-dependent interlayer interaction propagation processes in multiplex networks with an arbitrary number of layers, to more precisely depict the intertwined effects which bring challenges to the existing state-dependent interlayer interaction models. Specifically, the spreading rate of each node is regulated by the proposed spreading rate function (SRF) which depends on both the intrinsic dynamics in its layer and the infection probabilities of its counterparts. We propose an algorithm to obtain the spreading threshold of each layer of the proposed theoretical framework. We analyze the three-layer tuberculosis-awareness-flu model with the SRF of each node being the expectation of infection-probability-dependent spreading rate. This paper gives a thorough and detailed numerical investigation of the impact and interaction of system settings and the spreading threshold of each layer. We find that for tuberculosis spreading which is in competing relation with awareness and cooperation relation with flu, the epidemic threshold is a constant when other layers’ intrinsic spreading rates are small. The cooperation layer has dramatic influence on the constant while the competing layer has no effect on it. [ABSTRACT FROM AUTHOR]
- Published
- 2021
- Full Text
- View/download PDF
10. Infinite Families of Linear Codes Supporting More t -Designs.
- Author
-
Yan, Qianqian and Zhou, Junling
- Subjects
- *
AUTOMORPHISM groups , *CYBERNETICS , *AUTOMORPHISMS , *LINEAR codes - Abstract
Tang and Ding [IEEE IT 67 (2021) 244-254] studied the class of BCH codes $\mathcal {C}_{(q,q+1,4,1)}$ and their dual codes with $q=2^{m}$ and established that the codewords of the minimum (or the second minimum) weight in these codes support 4-designs or 3-designs. Motivated by this, we further investigate the codewords of the next adjacent weight in such codes and discover more infinite classes of $t$ -designs with $t=3,4$. In particular, we prove that codewords of weight 7 in $\mathcal {C}_{(q,q+1,4,1)}$ support 4-designs for odd $m \geqslant 5$ and they support 3-designs for even $m \geqslant 4$ , which provide infinite classes of simple $t$ -designs with new parameters. Another significant class of $t$ -designs we produce in this paper has complementary designs with parameters 4- $(2^{2s+1}+ 1,5,5)$ ; these designs have the smallest index among all the known simple 4- $(q+1,5,\lambda)$ designs derived from codes for prime powers $q$ ; and they are further proved to be isomorphic to the 4-designs admitting the projective general linear group PGL $(2,2^{2s+1})$ as the automorphism group constructed by Alltop in 1969. [ABSTRACT FROM AUTHOR]
- Published
- 2022
- Full Text
- View/download PDF
11. Twisted Reed–Solomon Codes.
- Author
-
Beelen, Peter, Puchinger, Sven, and Rosenkilde, Johan
- Subjects
- *
REED-Solomon codes , *HAMMING codes - Abstract
In this article, we present a new construction of evaluation codes in the Hamming metric, which we call twisted Reed–Solomon codes. Whereas Reed–Solomon (RS) codes are MDS codes, this need not be the case for twisted RS codes. Nonetheless, we show that our construction yields several families of MDS codes. Further, for a large subclass of (MDS) twisted RS codes, we show that the new codes are not generalized RS codes. To achieve this, we use properties of Schur squares of codes as well as an explicit description of the dual of a large subclass of our codes. We conclude the paper with a description of a decoder, that performs very well in practice as shown by extensive simulation results. [ABSTRACT FROM AUTHOR]
- Published
- 2022
- Full Text
- View/download PDF
12. Codes, Differentially $\delta$ -Uniform Functions, and $t$ -Designs.
- Author
-
Tang, Chunming, Ding, Cunsheng, and Xiong, Maosheng
- Subjects
- *
BINARY codes , *LINEAR codes , *CODING theory , *BOOLEAN functions , *AUTOMORPHISM groups , *STEINER systems , *LINEAR algebraic groups - Abstract
Boolean functions, coding theory and $t$ -designs have close connections and interesting interplay. A standard approach to constructing $t$ -designs is the use of linear codes with certain regularity. The Assmus-Mattson Theorem and the automorphism groups are two ways for proving that a code has sufficient regularity for supporting $t$ -designs. However, some linear codes hold $t$ -designs, although they do not satisfy the conditions in the Assmus-Mattson Theorem and do not admit a $t$ -transitive or $t$ -homogeneous group as a subgroup of their automorphisms. The major objective of this paper is to develop a theory for explaining such codes and obtaining such new codes and hence new $t$ -designs. To this end, a general theory for punctured and shortened codes of linear codes supporting $t$ -designs is established, a generalized Assmus-Mattson theorem is developed, and a link between 2-designs and differentially $\delta $ -uniform functions and 2-designs is built. With these general results, binary codes with new parameters and explicit weight distributions are obtained, new 2-designs and Steiner system $S(2, 4, 2^{n})$ are produced in this paper. [ABSTRACT FROM AUTHOR]
- Published
- 2020
- Full Text
- View/download PDF
13. A Generic Transformation for Optimal Node Repair in MDS Array Codes Over F 2.
- Author
-
Li, Jie, Tang, Xiaohu, and Hollanti, Camilla
- Subjects
- *
LINEAR codes , *REPAIRING , *BANDWIDTHS - Abstract
For high-rate linear systematic maximum distance separable (MDS) codes, most early constructions could initially optimally repair all the systematic nodes but not all the parity nodes. Fortunately, this issue was first solved by Li et al. in (IEEE Trans. Inform. Theory, 64(9), 6257-6267, 2018), where a transformation that can convert any nonbinary MDS array code into another one with desired properties was proposed. However, the transformation does not work for binary MDS array codes. In this paper, we address this issue by proposing another generic transformation that can convert any $[n, k]$ binary MDS array code into a new one, which endows any $r=n-k\ge 2$ chosen nodes with optimal repair bandwidth and optimal rebuilding access properties, and at the same time, preserves the normalized repair bandwidth/rebuilding access for the remaining $k$ nodes under some conditions. As two immediate applications, we show that 1) by applying the transformation multiple times, any binary MDS array code can be converted into one with optimal rebuilding access for all nodes, 2) any binary MDS array code with optimal repair bandwidth or optimal rebuilding access for the systematic nodes can be converted into one with the corresponding optimality property for all nodes. [ABSTRACT FROM AUTHOR]
- Published
- 2022
- Full Text
- View/download PDF
14. Constructions of Optimal Uniform Wide-Gap Frequency-Hopping Sequences.
- Author
-
Li, Peihua, Fan, Cuiling, Mesnager, Sihem, Yang, Yang, and Zhou, Zhengchun
- Subjects
- *
TELECOMMUNICATION systems , *SPREAD spectrum communications , *UNIFORMITY - Abstract
In frequency hopping (FH) communication systems, frequency hopping sequences (FHSs) are crucial in determining the system’s anti-jamming performance. If FHSs can ensure a wide-gap between two adjacent frequency points to avoid the frequency points with high interference probability, it will significantly improve the FH communication system’s anti-interference ability. Moreover, if each frequency point appears at the same number of times in a sequence period, the system’s anti-electromagnetic interference will be enhanced. Therefore, it is desirable to employ FHSs with low Hamming autocorrelation, wide frequency-hopping gap, and good uniformity in practical applications. However, to the best of our knowledge, no such infinite classes of FHSs have been reported in the literature to date. This paper aims to present two constructions of uniform wide-gap frequency-hopping sequences (WGFHSs) by concatenating two or three adequately designed sequences. For the first time, we obtain two infinite classes of WGFHSs, which are optimal with respect to the well-known Lempel-Greenberger bound. [ABSTRACT FROM AUTHOR]
- Published
- 2022
- Full Text
- View/download PDF
15. Almost-Reed–Muller Codes Achieve Constant Rates for Random Errors.
- Author
-
Abbe, Emmanuel, Hazla, Jan, and Nachum, Ido
- Subjects
- *
REED-Muller codes , *LINEAR codes , *ERROR rates , *ERROR probability - Abstract
This paper considers “ $\delta $ -almost Reed–Muller codes”, i.e., linear codes spanned by evaluations of all but a $\delta $ fraction of monomials of degree at most $d$. It is shown that for any $\delta > 0$ and any $\varepsilon >0$ , there exists a family of $\delta $ -almost Reed–Muller codes of constant rate that correct $1/2- \varepsilon $ fraction of random errors with high probability. For exact Reed–Muller codes, the analogous result is not known and represents a weaker version of the longstanding conjecture that Reed–Muller codes achieve capacity for random errors (Abbe-Shpilka-Wigderson STOC ’15). Our proof is based on the recent polarization result for Reed–Muller codes, combined with a combinatorial approach to establishing inequalities between the Reed–Muller code entropies. [ABSTRACT FROM AUTHOR]
- Published
- 2021
- Full Text
- View/download PDF
16. The Expansion Complexity of Ultimately Periodic Sequences Over Finite Fields.
- Author
-
Sun, Zhimin, Zeng, Xiangyong, Li, Chunlei, Zhang, Yi, and Yi, Lin
- Subjects
- *
SHIFT registers , *COMPLEXITY (Philosophy) - Abstract
The expansion complexity is a new figure of merit for cryptographic sequences. In this paper, we present an explicit formula of the (irreducible) expansion complexity of ultimately periodic sequences over finite fields. We also provide improved upper and lower bounds on the $N$ th irreducible expansion complexity when they are not explicitly determined. In addition, for some infinite sequences with given nonlinear complexity, a tighter upper bound of their $N$ th expansion complexity is given. [ABSTRACT FROM AUTHOR]
- Published
- 2021
- Full Text
- View/download PDF
17. New Results on Asymmetric Single Correcting Codes of Magnitude Four.
- Author
-
Xie, Derong and Luo, Jinquan
- Subjects
- *
FLASH memory , *MICROELECTROMECHANICAL systems , *NONVOLATILE memory , *ERROR-correcting codes - Abstract
An error model with asymmetric single error with magnitude four is considered. In this paper, the constructions of codes correcting single error of magnitude four over $\mathbb {Z}_{2^{{a}}3^{{b}}{r}}$ are studied which is equivalent to construct $B_{1}[{4}](2^{{a}}3^{{b}}{r})$ sets. Firstly, we reduce the construction of a maximal size ${B}_{1}[{4}](2^{{a}}3^{{b}}{r})$ set for ${a}\geq 4$ and $ \gcd ({r},6)=1$ to the construction of a maximal size ${B}_{1}[{4}](2^{{a}-3}3^{{b}}{r})$ set. Furthermore, we will show that maximal size ${B}_{1}[{4}](8\cdot 3^{{b}}{r})$ sets can be reduced to maximal size ${B}_{1}[{4}](3^{{b}}{r})$ sets and also give lower bounds of maximal size ${B}_{1}[{4}](12{r})$ and ${B}_{1}[{4}](2\cdot 3^{{b}}{r})$ sets. Finally, we give a necessary and sufficient condition on the existence of perfect ${B}_{1}[{4}]({p})$ set for prime $p$. [ABSTRACT FROM AUTHOR]
- Published
- 2021
- Full Text
- View/download PDF
18. On Cyclic Codes of Composite Length and the Minimum Distance II.
- Author
-
Xiong, Maosheng and Zhang, Aixian
- Subjects
- *
CYCLIC codes , *HAMMING distance , *LINEAR codes , *MAXIMA & minima , *CONGRUENCES & residues - Abstract
In this paper, we provide two complementary results for cyclic codes of composite length. First, we give a general construction of cyclic codes of length nr from cyclic codes of length n and a lower bound on the minimum distance. Numerical data show that many cyclic codes of composite length with the best parameters can be obtained in this way. Second, in the other direction, we show that for cyclic codes of length n with a primitive n-th root of unity as a non-zero, the minimum distance is roughly bounded by the square-free part of n. This means that we shall not expect good cyclic codes of length n in general if, for example, the length n is divisible by a high power of a prime. [ABSTRACT FROM AUTHOR]
- Published
- 2021
- Full Text
- View/download PDF
19. Binary LCD Codes and Self-Orthogonal Codes From a Generic Construction.
- Author
-
Zhou, Zhengchun, Li, Xia, Tang, Chunming, and Ding, Cunsheng
- Subjects
- *
LINEAR codes , *INJECTIONS , *POLYNOMIALS , *BINARY codes , *GENERIC drugs - Abstract
Linear codes with certain special properties have received renewed attention in recent years due to their practical applications. Among them, binary linear complementary dual (LCD) codes play an important role in implementations against side-channel attacks and fault injection attacks. Self-orthogonal codes can be used to construct quantum codes. In this paper, four classes of binary linear codes are constructed via a generic construction which has been intensively investigated in the past decade. Simple characterizations of these linear codes to be LCD or self-orthogonal are presented. Resultantly, infinite families of binary LCD codes and self-orthogonal codes are obtained. Infinite families of binary LCD codes from the duals of these four classes of linear codes are produced. Many LCD codes and self-orthogonal codes obtained in this paper are optimal or almost optimal in the sense that they meet certain bounds on general linear codes. In addition, the weight distributions of two sub-families of the proposed linear codes are established in terms of Krawtchouk polynomials. [ABSTRACT FROM AUTHOR]
- Published
- 2019
- Full Text
- View/download PDF
20. Capacity Characterization for State-Dependent Gaussian Channel With a Helper.
- Author
-
Sun, Yunhao, Duan, Ruchen, Liang, Yingbin, Khisti, Ashish, and Shamai Shitz, Shlomo
- Subjects
- *
GAUSSIAN channels , *TRANSMITTERS (Communication) , *ARBITRARY constants , *MATHEMATICAL constants , *MATHEMATICS - Abstract
The state-dependent point-to-point Gaussian channel with a helper is first studied, in which a transmitter communicates with a receiver via a state-corrupted channel. The state is not known to the transmitter nor to the receiver, but known to a helper noncausally, which then wishes to assist the receiver to cancel the state. Differently from the previous work that characterized the capacity only in the infinite state power regime, this paper explores the general case with arbitrary state power. A lower bound on the capacity is derived based on an achievable scheme that integrates direct state subtraction and single-bin dirty paper coding. By analyzing this lower bound and further comparing it with the existing upper bounds, the capacity of the channel is characterized for a wide range of channel parameters. Such an idea of characterizing the capacity is further extended to study the two-user state-dependent multiple access channel with a helper. By comparing the derived inner and outer bounds, the channel parameters are partitioned into appropriate cases, and for each case, either segments on the capacity region boundary or the full capacity region are characterized. [ABSTRACT FROM PUBLISHER]
- Published
- 2016
- Full Text
- View/download PDF
21. Topological Structure, Reachability, and Stabilization of Constrained Boolean Control Networks via Event-Triggered Control.
- Author
-
Lin, Lin, Cao, Jinde, Abdel-Aty, Mahmoud, and Al-Juboori, Udai Ali
- Subjects
- *
ESCHERICHIA coli , *SWARM intelligence , *STATE feedback (Feedback control systems) , *ALGORITHMS - Abstract
This paper is concerned with the topological structure, reachability, and stabilization for Boolean control networks (BCNs) with state constraints via event-triggered control (ETC) scheme. In the first part, the topological structure of BCNs with state constraints is studied. Under the framework of state constrain, the definitions of fixed point and cycle are first defined. A novel phenomenon is that there may exist two kinds constrained fixed points, which are, respectively, named as the livelock and deadlock ones. It is different with the traditional fixed point. Accordingly, a formula is presented to calculate the number of constrained fixed points and constrained cycles. In the second part, the constrained reachability and stabilization problem of the event-triggered controlled BCNs are investigated. Two necessary and sufficient criteria are, respectively, obtained. Furthermore, an algorithm is developed to design all feasible controllers. Finally, a reduced model of the lac operon in the Escherichia coli is shown to illustrate the efficiency of the obtained results. [ABSTRACT FROM AUTHOR]
- Published
- 2021
- Full Text
- View/download PDF
22. A Systematic Construction of MDS Codes With Small Sub-Packetization Level and Near-Optimal Repair Bandwidth.
- Author
-
Li, Jie, Liu, Yi, and Tang, Xiaohu
- Subjects
- *
BANDWIDTHS , *FINITE fields , *TWO-dimensional bar codes - Abstract
In the literature, all the known high-rate MDS codes with the optimal repair bandwidth possess a significantly large sub-packetization level, which may prevent the codes to be implemented in practical systems. To build MDS codes with small sub-packetization level, existing constructions and theoretical bounds imply that one may sacrifice the optimality of the repair bandwidth. Partly motivated by the work of Tamo et al. (IEEE Trans. Inform. Theory, 59(3), 1597–1616, 2013), in this paper, we present a transformation that can greatly reduce the sub-packetization level of MDS codes with the optimal repair bandwidth with respect to the same code length n. As applications of the transformation, four high-rate MDS codes having both small sub-packetization level and near-optimal repair bandwidth can be obtained, where three of them are explicit and the required field sizes are around or even smaller than the code length ${n}$. Additionally, we propose another explicit MDS code which has a similar structure as that of the first resultant code obtained by the generic transformation, but can be built on a smaller finite field. [ABSTRACT FROM AUTHOR]
- Published
- 2021
- Full Text
- View/download PDF
23. A Double-Blind Anonymous Evaluation-Based Trust Model in Cloud Computing Environments.
- Author
-
Zhang, Peiyun, Zhou, Mengchu, and Kong, Yang
- Subjects
- *
CLOUD computing , *HELPING behavior , *TRUST , *COMPUTER systems , *DECEPTION , *FUZZY graphs , *FUZZY mathematics - Abstract
In the last ten years, cloud services provided many applications in various areas. Most of them are hosted in a heterogeneous distributed large-scale cloud computing environment and face inherent uncertainty, unreliability, and malicious attacks that trouble both service users and providers. To solve the problems of malicious attacks (including solo and collusion deception ones) in a public cloud computing environment, we for the first time propose a double-blind anonymous evaluation-based trust model. Based on it, cloud service providers and users are anonymously matched according to user requirements. It can be used to effectively handle some malicious attacks that intend to distort trust evaluations. Providers may secretly hide gain-sharing information into service results and send the results to users to ask for higher trust evaluations than their deserved ones. This paper proposes to adopt checking nodes to help detect such behavior. It then conducts gain–loss analysis for providers who intend to perform provider–user collusion deception. The proposed trust model can be used to effectively help one recognize collusion deception behavior and allow policy-makers to set suitable loss to punish malicious providers. Consequently, provider-initiated collusion deception behavior can be greatly discouraged in public cloud computing systems. Simulation results show that the proposed method outperform two updated methods, i.e., one based on fail-stop signature and another based on fuzzy mathematics in terms of malicious node detection ratio and speed. [ABSTRACT FROM AUTHOR]
- Published
- 2021
- Full Text
- View/download PDF
24. On the Global Minimizers of Real Robust Phase Retrieval With Sparse Noise.
- Author
-
Aravkin, Aleksandr, Burke, James V., and He, Daiwei
- Subjects
- *
COMPRESSED sensing , *TWO-dimensional bar codes , *INFORMATION theory , *NOISE , *NOISE measurement , *RANDOM noise theory - Abstract
We study a class of real robust phase retrieval problems under a Gaussian assumption on the coding matrix when the received signal is sparsely corrupted by noise. The goal is to establish conditions on the sparsity under which the input vector can be exactly recovered. The recovery problem is formulated as residual minimization in the $\ell _{1}$ -norm. The main contribution is a robust phase retrieval counterpart to the seminal paper by Candes and Tao on compressed sensing ($\ell _{1}$ regression) [Decoding by linear programming. IEEE Transactions on Information Theory, 51(12):4203–4215, 2005]. The analysis depends on a key new property of the coding matrix called the Absolute Range Property (ARP) which is the analogue to the Null Space Property (NSP) in compressed sensing. When the residuals are computed using squared magnitudes, we show that ARP follows from a standard Restricted Isometry Property (RIP). However, when the residuals are computed using absolute magnitudes, a different kind of RIP or growth property is required. We conclude by showing that the robust phase retrieval objectives are sharp with respect to their minimizers with high probability. [ABSTRACT FROM AUTHOR]
- Published
- 2021
- Full Text
- View/download PDF
25. Comments on Cut-Set Bounds on Network Function Computation.
- Author
-
Huang, Cupjin, Tan, Zihan, Yang, Shenghao, and Guang, Xuan
- Subjects
- *
LINEAR network coding , *COMPUTER systems , *INFORMATION theory , *TOPOLOGY , *MATHEMATICS - Abstract
A function computation problem over a directed acyclic network has been considered in the literature, where a sink node is required to compute a target function correctly with the inputs arbitrarily generated at multiple source nodes. The network links are error free but capacity limited, and the intermediate nodes perform network coding. The computing rate of a network code is the average number of times that the target function is computed for one use of the network, i.e., each link in the network is used at most once. In the existing papers, two cut-set bounds were proposed on the computing rate. However, we in this paper show that these bounds are not valid for general network function computation problems. We analyze the reason of the invalidity and propose a general cut-set bound by using a new equivalence relation associated with the inputs of the target function. Moreover, some results in the existing papers were proved by applying the invalid upper bound. We also justify the validity of these results. [ABSTRACT FROM AUTHOR]
- Published
- 2018
- Full Text
- View/download PDF
26. PAPR Problem for Walsh Systems and Related Problems.
- Author
-
Boche, Holger and Tampubolon, Ezra
- Subjects
- *
SIGNAL processing , *WIRELESS communications , *ENERGY consumption , *POWER resources , *CODE division multiple access , *ARITHMETIC series - Abstract
High peak values of transmission signals in wireless communication systems lead to wasteful energy consumption and degradation of several transmission performances. We continue the theoretical contributions made by Boche and Farell toward the understanding of peak value reduction, using the strategy known as tone reservation for orthogonal transmission schemes. There it was shown that for orthogonal frequency-division multiplexing (OFDM) systems, the combinatorial object called arithmetic progression plays an important role in setting limitations for the applicability of the tone reservation method. In this paper, we show that the combinatorial object introduced as perfect Walsh sum (PWS) plays a similar role for code-division multiple access (CDMA) systems as arithmetic progression for OFDM systems. By specific construction, we show that for a chosen numbers $m$ and $n$ , all subsets $\mathcal {I} $ of the set $[N]$ of the first $N=2^{n}$ natural numbers, which has the density in $[N]$ larger than a given $\delta \in (0,1)$ , i.e., $\left |{ \mathcal {I} }\right |/N\geq \delta $ , and which is sufficiently large enough, in the sense that $\left |{ I }\right |\geq 2(2/\delta)^{2^{m}-1}$ , contains a PWS of size $2^{m}$. By means of this result, and motivated by the previously mentioned connection between arithmetic progression and PWS, we show results for the PWS which are analogous to the famous Szemerédi theorem on arithmetic progressions, Conlon-Gower’s theorem on probabilistic construction of “sparse” sets containing an arithmetic progression, and even a solution of an analogon to the Erdős’ conjecture on arithmetic progressions. Those results give in particular an insight into the asymptotic limitations of tone reservation method for the CDMA systems. Besides, we show that a subset $I$ of $[N]$ is a PWS if and only if the embedding inequality of the subspace of $L^{1}([{0,1}])$ , containing linear combinations of Walsh functions indexed by elements of $\mathcal {I} $ , holds with the minimum possible embedding constant $\sqrt { \left |{ \mathcal {I} }\right |}$. The corresponding approach based in particular by the fact that the PWSs are the only Walsh sums having unit $L^{1}$ -norm, proven in this paper. By means of that results, we show that the minimum possible threshold constant for which the tone reservation method is applicable yields $\sqrt { \left |{ \mathcal {I} }\right |}$ if and only if the information set $\mathcal {I} $ is a PWS. [ABSTRACT FROM AUTHOR]
- Published
- 2018
- Full Text
- View/download PDF
27. A Possible Way to Perform Recursive Bayesian Estimate in the Possibility Domain.
- Author
-
Jiang, Wei, Ferrero, Alessandro, Salicone, Simona, and Zhang, Qi
- Subjects
- *
GENERALIZATION , *BAYESIAN analysis , *RANDOM variables , *POSSIBILITY , *MATHEMATICS - Abstract
This paper defines a generalization of the recursive Bayesian estimate (RBE), within the mathematical possibility theory. This generalization is motivated by the fact that the classical RBE, by design, deals only with random variables and can only provide closed-form solution for a few cases. The possibilistic generalization is based on the random-fuzzy variables, thus allowing one to take into account, in a very natural way, both random and systematic contributions to the uncertainty and to implement the RBE for any distribution of system state variables in a simple way. This paper illustrates the advantages of the proposed generalization, by presenting both the theoretical development, and a detailed application example. [ABSTRACT FROM AUTHOR]
- Published
- 2017
- Full Text
- View/download PDF
28. Narrow-Sense BCH Codes Over \mathrm GF(q) With Length n=\frac q^m-1q-1.
- Author
-
Li, Shuxing, Ding, Cunsheng, Xiong, Maosheng, and Ge, Gennian
- Subjects
- *
CYCLIC codes , *QUADRATIC forms , *BCH codes , *DECODING algorithms , *TELECOMMUNICATION systems - Abstract
Cyclic codes are widely employed in communication systems, storage devices, and consumer electronics, as they have efficient encoding and decoding algorithms. BCH codes, as a special subclass of cyclic codes, are in most cases among the best cyclic codes. A subclass of good BCH codes are the narrow-sense BCH codes over \mathrm GF(q) with length n=(q^m-1)/(q-1) . Little is known about this class of BCH codes when $q>2$ . The objective of this paper is to study some of the codes within this class. In particular, the dimension, the minimum distance, and the weight distribution of some ternary BCH codes with length n=(3^{m}-1)/2 are determined in this paper. A class of ternary BCH codes meeting the Griesmer bound is identified. An application of some of the BCH codes in secret sharing is also investigated. [ABSTRACT FROM PUBLISHER]
- Published
- 2017
- Full Text
- View/download PDF
29. Design of Resilient Reliable Dissipativity Control for Systems With Actuator Faults and Probabilistic Time-Delay Signals via Sampled-Data Approach.
- Author
-
Manivannan, R., Samidurai, R., Cao, Jinde, and Perc, Matjaz
- Subjects
- *
SERVOMECHANISMS , *RESILIENT design , *LINEAR matrix inequalities , *ACTUATORS , *BINOMIAL distribution , *INTEGRAL inequalities - Abstract
The issue of resilient reliable dissipativity performance index for systems including actuator faults and probabilistic time-delay signals via sampled-data control approach is investigated. Specifically, random variables governed by the Bernoulli distribution are examined in detail for the random time-delay signals. By using the Lyapunov–Krasovskii functionals together with the Wirtinger double integral inequality approach and reciprocally convex combination technique, which reflects complete information on the certain random sampling; as a result, a new set of sufficient criterion is launched to ensure that the proposed closed-loop system is strictly ${(\mathbb {Q},\mathbb {S},\mathbb {R})}$ - ${\gamma }$ -dissipative. The proposed criterion for dissipativity-based resilient reliable controller is expressed in the form of linear matrix inequalities. The major contributions of this paper is ${(\mathbb {Q},\mathbb {S},\mathbb {R})}$ - ${\gamma }$ -dissipativity concept can be adopted to analyze more dynamical performances simultaneously, such as ${\mathcal {H}_\infty }$ , passivity, mixed ${\mathcal {H}_\infty }$ , and passivity performance for the proposed system model by choosing the weighting matrices ${(\mathbb {Q},\mathbb {S},\mathbb {R})}$. Finally, an interesting simulation example is demonstrated to showing the applicability and effectiveness of the theoretical results together with proposed control law by taking the experimental values of the high-incidence research model and rotary servo system. [ABSTRACT FROM AUTHOR]
- Published
- 2020
- Full Text
- View/download PDF
30. Coreness and $h$ -Index for Weighted Networks.
- Author
-
Wu, Xiaoqun, Wei, Wenbin, Tang, Longkun, Lu, Jun'an, and Lu, Jinhu
- Subjects
- *
DECOMPOSITION method , *NETWORK performance , *DEFINITIONS , *ELECTRIC power distribution grids - Abstract
This paper presents a unified framework to generalize the traditional $k$ -core decomposition method for both weighted and unweighted networks. It not only subsumes previous $k$ -core decomposition methods but provides some new ones. With the help of the definition of $n$ -th order h-index, we prove that all $k$ -core indexes can be regarded as some steady state of h-index series with $n$ going to infinity. Furthermore, all $h$ -indexes we obtain in intermediate calculation steps can be used as ranking scores to assess node importance in networks. Finally, we apply the provided new methods as well as two existing ones to four real networks and compare their performances on spreading influences ranking. [ABSTRACT FROM AUTHOR]
- Published
- 2019
- Full Text
- View/download PDF
31. Constructing APN Functions Through Isotopic Shifts.
- Author
-
Budaghyan, Lilya, Calderini, Marco, Carlet, Claude, Coulter, Robert S., and Villa, Irene
- Subjects
- *
INFORMATION theory , *CODING theory , *BOOLEAN functions , *MATHEMATICAL equivalence , *MATHEMATICS - Abstract
Almost perfect nonlinear (APN) functions over fields of characteristic 2 play an important role in cryptography, coding theory and, more generally, mathematics and information theory. In this paper we deduce a new method for constructing APN functions by studying the isotopic equivalence, concept defined for quadratic planar functions in fields of odd characteristic. In particular, we construct a family of quadratic APN functions which provides a new example of an APN mapping over ${\mathbb F}_{2^{9}}$ and includes an example of another APN function $x^{9}+ \mathop {\mathrm {Tr}}\nolimits (x^{3})$ over ${\mathbb F}_{2^{8}}$ , known since 2006 and not classified up to now. We conjecture that the conditions for this family are satisfied by infinitely many APN functions. [ABSTRACT FROM AUTHOR]
- Published
- 2020
- Full Text
- View/download PDF
32. Towards Practical Private Information Retrieval From MDS Array Codes.
- Author
-
Li, Jie, Karpuk, David, and Hollanti, Camilla
- Subjects
- *
INFORMATION retrieval , *TWO-dimensional bar codes , *CIPHERS , *BANDWIDTHS - Abstract
Private information retrieval (PIR) is the problem of privately retrieving one out of $M$ original files from $N$ severs, i.e., each individual server gains no information on the identity of the file that the user is requesting. Usually, the $M$ files are replicated or encoded by a maximum distance separable (MDS) code and then stored across the $N$ servers. Compared to mere replication, MDS-coded servers can significantly reduce the storage overhead. Particularly, PIR from minimum storage regenerating (MSR) coded servers can simultaneously reduce the repair bandwidth when repairing failed servers. Existing PIR protocols from MSR-coded servers either require large sub-packetization levels or are not capacity-achieving. In this paper, a PIR protocol from MDS array codes is proposed, subsuming PIR from MSR-coded servers as a special case. Particularly, only the case of non-colluding, honest-but-curious servers is considered. The retrieval rate of the new PIR protocol achieves the capacity of PIR from MDS-/MSR-coded servers. By choosing different MDS array codes, the new PIR protocol can have varying advantages when compared with existing protocols, e.g., 1) small sub-packetization, 2) (near-)optimal repair bandwidth, 3) implementable over the binary field $\mathbf {F}_{2}$. [ABSTRACT FROM AUTHOR]
- Published
- 2020
- Full Text
- View/download PDF
33. Optimal Cyclic Codes With Hierarchical Locality.
- Author
-
Luo, Gaojun and Cao, Xiwang
- Subjects
- *
CYCLIC codes , *REED-Solomon codes , *LINEAR codes - Abstract
By introducing several levels of recoverability for locally recoverable codes (LRCs), LRCs with hierarchical locality (H-LRCs) are defined for correcting different numbers of erasures. There are two major ingredients in this paper. The first is to investigate some properties and existence conditions of optimal H-LRCs with respect to a generalized Singleton-like bound for H-LRCs. The second ingredient is to propose several constructions of optimal H-LRCs by employing cyclic codes. Notably, the parameters of these optimal H-LRCs are flexible. [ABSTRACT FROM AUTHOR]
- Published
- 2020
- Full Text
- View/download PDF
34. A Class of Quadrinomial Permutations With Boomerang Uniformity Four.
- Author
-
Tu, Ziran, Li, Nian, Zeng, Xiangyong, and Zhou, Junchao
- Subjects
- *
BLOCK ciphers , *UNIFORMITY , *PERMUTATIONS , *CRYPTOGRAPHY , *FINITE fields - Abstract
In Eurocrypt’18, Cid et al. proposed a new cryptanalysis tool called Boomerang Connectivity Table (BCT), to evaluate S-boxes of block ciphers. Later, Boura and Canteaut further investigated the new parameter Boomerang uniformity for cryptographic S-boxes. It is of great interest to find new S-boxes with low Boomerang uniformity for even dimensions. In this paper, we prove that a class of permutation quadrinomials over $\mathbb {F}_{2^{2m}}$ with $m$ odd has Boomerang uniformity four, which gives the fifth class of such kind of permutation polynomials. Further, the occurrences of 0 and 4 in the BCTs of the investigated permutation polynomials are also completely determined. [ABSTRACT FROM AUTHOR]
- Published
- 2020
- Full Text
- View/download PDF
35. K-Plex 2-Erasure Codes and Blackburn Partial Latin Squares.
- Author
-
Stones, Rebecca J.
- Subjects
- *
MAGIC squares , *CIPHERS - Abstract
A k-plex of order n is an ${n} \times {n}$ matrix on n symbols, where every row contains k distinct symbols, every column contains k distinct symbols, and every symbol occurs exactly k times. Yi et al. (2019) introduced 3-plex codes which are 2-erasure codes (2-erasure tolerant array codes) derived from 3-plexes. In this paper, we generalize 3-plex codes to k-plex codes. We introduce the notion of a “strong” k-plex which implies the derived k-plex code is 2-erasure tolerant. Moreover, k-plex codes derived from strong $k$ -plexes have a straightforward algorithm for reconstruction. These general k-plex codes offer greater flexibility when choosing a suitable code for a storage system, enabling the operator to better optimize the unavoidable trade-offs involved. Blackburn asked for the maximum number of entries in an ${n} \times {n}$ partial Latin square on n symbols in which if distinct cells $({i},{j})$ and $({i}',{j}')$ contain the same symbol, then the cells $({i}',{j})$ and $({i},{j}')$ are empty. A “strong” k-plex satisfies the Blackburn property (along with two other properties related to erasure coding). We investigate the necessary conditions for the existence of Blackburn k-plexes (and hence necessary conditions for the existence of strong k-plexes). We show that any Blackburn k-plex has order ${n} \geq \lceil (\sqrt {2}+1){k}-2 \rceil $. We describe how to construct strong k-plexes of order n when $k \in \{2,3,4,5\}$ for all possible orders n, and we give a simple construction of strong k-plexes of order ${k}^{2}$ for $k \geq 2$. [ABSTRACT FROM AUTHOR]
- Published
- 2020
- Full Text
- View/download PDF
36. Euclidean and Hermitian Hulls of MDS Codes and Their Applications to EAQECCs.
- Author
-
Fang, Weijun, Fu, Fang-Wei, Li, Lanqiang, and Zhu, Shixin
- Subjects
- *
ERROR-correcting codes , *BINARY codes , *REED-Solomon codes , *LIQUID crystal displays , *CIPHERS , *LINEAR codes - Abstract
In this paper, we construct several classes of maximum distance separable (MDS) codes via generalized Reed-Solomon (GRS) codes and extended GRS codes, where we can determine the dimensions of their Euclidean hulls or Hermitian hulls. It turns out that the dimensions of Euclidean hulls or Hermitian hulls of the codes in our constructions can take all or almost all possible values. As a consequence, we can apply our results to entanglement-assisted quantum error-correcting codes (EAQECCs) and obtain several new families of MDS EAQECCs with flexible parameters. The required number of maximally entangled states of these MDS EAQECCs can take all or almost all possible values. Moreover, several new classes of q-ary MDS EAQECCs of length $ {n} > {q}+1$ are also obtained. [ABSTRACT FROM AUTHOR]
- Published
- 2020
- Full Text
- View/download PDF
37. Sampled-Data State Feedback Control for the Set Stabilization of Boolean Control Networks.
- Author
-
Zhu, Shiyong, Liu, Yang, Lou, Jungang, Lu, Jianquan, and Alsaadi, Fuad E.
- Subjects
- *
STATE feedback (Feedback control systems) , *INVARIANT sets , *POINT set theory - Abstract
This paper studies the set stabilization of Boolean control networks (BCNs) under sampled-data state feedback control (SDSFC). The main research content is divided into two parts. First, the topological structure of BCNs under given SDSFC is investigated. The fixed point and sampled cycle are defined, respectively. It is found that sampled cycles allow elements to be repeated and not every element can be regarded as an initial state, and this is quite different from conventional cycles of BCNs. A theorem is presented to calculate the number of fixed points and an algorithm is given to find all fixed points and sampled cycles. Second, the set stabilization problem of BCNs by SDSFC is investigated based on the sampled point set and the sampled point control invariant set (SPCIS). A necessary and sufficient condition is derived for the global set stabilization of BCNs by SDSFC, and further sampled-data state feedback controllers are also designed. The interesting thing is that if a state enters the SPCIS as an unsampled point, then it may run out of the given set again, which is in sharp contrast to conventional BCNs. Finally, an example is given to illustrate the efficiency of the obtained results. [ABSTRACT FROM AUTHOR]
- Published
- 2020
- Full Text
- View/download PDF
38. Several Classes of Minimal Linear Codes With Few Weights From Weakly Regular Plateaued Functions.
- Author
-
Mesnager, Sihem and Sinak, Ahmet
- Subjects
- *
FINITE fields , *INFORMATION theory , *HAMMING weight , *LINEAR codes - Abstract
Minimal linear codes have significant applications in secret sharing schemes and secure two-party computation. There are several methods to construct linear codes, one of which is based on functions over finite fields. Recently, many construction methods for linear codes from functions have been proposed in the literature. In this paper, we generalize the recent construction methods given by Tang et al. in [IEEE Transactions on Information Theory, 62(3), 1166-1176, 2016] to weakly regular plateaued functions over finite fields of odd characteristic. We first construct three-weight linear codes from weakly regular plateaued functions based on the second generic construction and then determine their weight distributions. We also give a punctured version and subcode of each constructed code. We note that they may be (almost) optimal codes and can be directly employed to obtain (democratic) secret sharing schemes, which have diverse applications in the industry. We next observe that the constructed codes are minimal for almost all cases and finally describe the access structures of the secret sharing schemes based on their dual codes. [ABSTRACT FROM AUTHOR]
- Published
- 2020
- Full Text
- View/download PDF
39. Ulam Ball Size Analysis for Permutation and Multipermutation Codes Correcting Translocation Errors.
- Author
-
Kong, Justin
- Subjects
- *
FLASH memory , *COMPUTER storage devices , *CIPHERS , *NONVOLATILE memory , *CHANNEL coding , *SOFTWARE measurement - Abstract
Permutation and multipermutation codes in the Ulam metric have been suggested for use in non-volatile memory storage systems such as flash memory devices. In this paper we introduce a new method to calculate permutation ball sizes in the Ulam metric using Young Tableaux and prove the non-existence of non-trivial perfect permutation codes in the Ulam metric. We then extend the study to multipermutations, providing upper and lower bounds on multipermutation Ulam ball sizes and resulting upper and lower bounds on the maximal size of multipermutation codes in the Ulam metric. [ABSTRACT FROM AUTHOR]
- Published
- 2019
- Full Text
- View/download PDF
40. Constructions of Involutions Over Finite Fields.
- Author
-
Zheng, Dabin, Yuan, Mu, Li, Nian, Hu, Lei, and Zeng, Xiangyong
- Subjects
- *
FINITE fields , *CODING theory , *LINEAR equations , *INFORMATION theory , *BLOCK ciphers , *POLYNOMIALS - Abstract
An involution over finite fields is a permutation polynomial whose inverse is itself. Owing to this property, involutions over finite fields have been widely used in applications, such as cryptography and coding theory. Following the idea by Wang to characterize the involutory behavior of the generalized cyclotomic mappings, this paper gives a more concise criterion for $x^{r}h(x^{s})\in {\mathbb F} _{q}[x]$ being involutions over the finite field ${\mathbb F}_{q}$ , where $r\geq 1$ and $s\,|\, (q-1)$. By using this criterion, we propose a general method to construct involutions of the form $x^{r}h(x^{s})$ over ${\mathbb F}_{q}$ from given involutions over some subgroups of ${\mathbb F}_{q}^{*}$ by solving congruent and linear equations over finite fields. Then, many classes of explicit involutions of the form $x^{r}h(x^{s})$ over ${\mathbb F}_{q}$ are obtained. [ABSTRACT FROM AUTHOR]
- Published
- 2019
- Full Text
- View/download PDF
41. An Ergodic Theory of Binary Operations—Part I: Key Properties.
- Author
-
Nasser, Rajai
- Subjects
- *
ERGODIC theory , *BINARY operations , *MATHEMATICS , *CONTINUOUS groups , *INVARIANT measures - Abstract
An open problem in polarization theory is to determine the binary operations that always lead to polarization (in the general multilevel sense) when they are used in Arıkan style constructions. This paper, which is presented in two parts, solves this problem by providing a necessary and sufficient condition for a binary operation to be polarizing. This (first) part of this paper introduces the mathematical framework that we will use in the second part to characterize the polarizing operations. We define uniformity preserving, irreducible, ergodic, and strongly ergodic operations, and we study their properties. The concepts of a stable partition and the residue of a stable partition are introduced. We show that an ergodic operation is strongly ergodic if and only if all its stable partitions are their own residues. We also study the products of binary operations and the structure of their stable partitions. We show that the product of a sequence of binary operations is strongly ergodic if and only if all the operations in the sequence are strongly ergodic. In the second part of this paper, we provide a foundation of polarization theory based on the ergodic theory of binary operations that we develop in this part. [ABSTRACT FROM PUBLISHER]
- Published
- 2016
- Full Text
- View/download PDF
42. Capacity of Two-Way Channels With Symmetry Properties.
- Author
-
Weng, Jian-Jia, Song, Lin, Alajaji, Fady, and Linder, Tamas
- Subjects
- *
SYMMETRY , *LINEAR network coding , *CHANNEL coding , *INFORMATION theory , *BROADCAST channels - Abstract
In this paper, we make use of channel symmetry properties to determine the capacity region of three types of two-way networks: 1) two-user memoryless two-way channels (TWCs); 2) two-user TWCs with memory; and 3) three-user multiaccess/degraded broadcast (MA/DB) TWCs. For each network, symmetry conditions under which a Shannon-type random coding inner bound (under independent non-adaptive inputs) is tight are given. For two-user memoryless TWCs, prior results are substantially generalized by viewing a TWC as two interacting state-dependent one-way channels. The capacity of symmetric TWCs with memory, whose outputs are functions of the inputs and independent stationary and ergodic noise processes, is also obtained. Moreover, various channel symmetry properties under which the Shannon-type inner bound is tight are identified for three-user MA/DB TWCs. The results not only enlarge the class of symmetric TWCs whose capacity region can be exactly determined but also imply that interactive adaptive coding, not improving capacity, is unnecessary for such channels. [ABSTRACT FROM AUTHOR]
- Published
- 2019
- Full Text
- View/download PDF
43. Generalized Single-Phase Harmonic State Space Modeling of the Modular Multilevel Converter With Zero-Sequence Voltage Compensation.
- Author
-
Xu, Zigao, Li, Binbin, Wang, Shengbo, Zhang, Shiguang, and Xu, Dianguo
- Subjects
- *
HARMONIC analysis (Mathematics) , *ELECTRIC controllers , *ELECTRIC potential , *MATHEMATICS , *SIMULATION methods & models - Abstract
The modular multilevel converter (MMC) has attracted extensive research in recent years. An appropriate model is necessary to analyze stability or to design MMC controllers. Several published MMC models have been derived in single-phase form to simplify the modeling mathematics. However, little attention is given to the zero-sequence voltage, which introduces coupling in the single-phase model and leads to significant error. In this paper, after revealing the mechanism behind the zero-sequence voltage, a more accurate generalized single-phase MMC model is proposed, which eliminates the zero-sequence voltage coupling effect and is linearized based on harmonic state space (HSS) theory to precisely characterize the internal harmonic features of MMC. A systematic HSS modeling process is presented for both open-loop and closed-loop conditions. And the proposed model is generalized as it can incorporate different control strategy by controller transfer function substitution. Hence it is valuable to analyze MMC stability and dynamics. Model effectiveness is verified by simulation results. [ABSTRACT FROM AUTHOR]
- Published
- 2019
- Full Text
- View/download PDF
44. A General Construction of Ordered Orthogonal Arrays Using LFSRs.
- Author
-
Panario, Daniel, Saaltink, Mark, Stevens, Brett, and Wevrick, Daniel
- Subjects
- *
ORTHOGONAL arrays , *SHIFT registers , *FINITE fields , *POLYNOMIALS , *CONSTRUCTION - Abstract
The $q^{t} \times (q+1)t$ ordered orthogonal arrays (OOAs) of strength $t$ over the alphabet $ \mathbb {F}_{q}$ were constructed using linear feedback shift register sequences (LFSRs) defined by primitive polynomials in $ \mathbb {F}_{q}[x]$. In this paper, we extend this result to all polynomials in $\mathbb {F}_{q}[x]$ which satisfy some fairly simple restrictions, i.e., the restrictions that are automatically satisfied by primitive polynomials. While these restrictions sometimes reduce the number of columns produced from $(q+1)t$ to a smaller multiple of $t$ , in many cases, we still obtain the maximum number of columns in the constructed OOA when using non-primitive polynomials. For $2 \le q \le 9$ and small $t$ , we generate OOAs in this manner for all permissible polynomials of degree $t$ in $ \mathbb {F}_{q}[x]$ and compare the results to the ones produced in , , and showing how close the arrays are to being “full” orthogonal arrays. Unusually for the finite fields, our arrays based on the non-primitive irreducible and even reducible polynomials are closer to the orthogonal arrays than those built from the primitive polynomials. [ABSTRACT FROM AUTHOR]
- Published
- 2019
- Full Text
- View/download PDF
45. Minimal Linear Codes in Odd Characteristic.
- Author
-
Bartoli, Daniele and Bonini, Matteo
- Subjects
- *
LINEAR codes , *HAMMING weight - Abstract
In this paper, we generalize constructions in two recent works of Ding, Heng, and Zhou to any field $\mathbb {F}_{{q}}$ , ${q}$ odd, providing infinite families of minimal codes for which the Ashikhmin–Barg bound does not hold. [ABSTRACT FROM AUTHOR]
- Published
- 2019
- Full Text
- View/download PDF
46. MDS Codes With Hulls of Arbitrary Dimensions and Their Quantum Error Correction.
- Author
-
Luo, Gaojun, Cao, Xiwang, and Chen, Xiaojing
- Subjects
- *
HAMMING codes , *QUANTUM entanglement , *LINEAR codes , *REED-Solomon codes , *ERROR-correcting codes - Abstract
The hull of linear codes has promising utilization in coding theory and quantum coding theory. In this paper, we study the hull of generalized Reed–Solomon codes and extended generalized Reed–Solomon codes over finite fields with respect to the Euclidean inner product. Several infinite families of MDS codes with hulls of arbitrary dimensions are presented. As an application, using these MDS codes with hulls of arbitrary dimensions, we construct several new infinite families of entanglement-assisted quantum error-correcting codes with flexible parameters. [ABSTRACT FROM AUTHOR]
- Published
- 2019
- Full Text
- View/download PDF
47. Non-Negative Matrix Factorizations for Multiplex Network Analysis.
- Author
-
Gligorijevic, Vladimir, Panagakis, Yannis, and Zafeiriou, Stefanos
- Subjects
- *
SYSTEM administrators , *MATRIX analytic methods , *FACTORIZATION , *MATHEMATICS , *INTEGRALS - Abstract
Networks have been a general tool for representing, analyzing, and modeling relational data arising in several domains. One of the most important aspect of network analysis is community detection or network clustering. Until recently, the major focus have been on discovering community structure in single (i.e., monoplex) networks. However, with the advent of relational data with multiple modalities, multiplex networks, i.e., networks composed of multiple layers representing different aspects of relations, have emerged. Consequently, community detection in multiplex network, i.e., detecting clusters of nodes shared by all layers, has become a new challenge. In this paper, we propose Network Fusion for Composite Community Extraction (NF-CCE), a new class of algorithms, based on four different non-negative matrix factorization models, capable of extracting composite communities in multiplex networks. Each algorithm works in two steps: first, it finds a non-negative, low-dimensional feature representation of each network layer; then, it fuses the feature representation of layers into a common non-negative, low-dimensional feature representation via collective factorization. The composite clusters are extracted from the common feature representation. We demonstrate the superior performance of our algorithms over the state-of-the-art methods on various types of multiplex networks, including biological, social, economic, citation, phone communication, and brain multiplex networks. [ABSTRACT FROM AUTHOR]
- Published
- 2019
- Full Text
- View/download PDF
48. Accurate 3D Reconstruction from Small Motion Clip for Rolling Shutter Cameras.
- Author
-
Im, Sunghoon, Ha, Hyowon, Choe, Gyeongmin, Joo, Kyungdon, Kweon, In So, and Jeon, Hae-Gon
- Subjects
- *
RECONSTRUCTION (Graph theory) , *GEOMETRY , *MATHEMATICS , *MOTION , *ALGORITHM research - Abstract
Structure from small motion has become an important topic in 3D computer vision as a method for estimating depth, since capturing the input is so user-friendly. However, major limitations exist with respect to the form of depth uncertainty, due to the narrow baseline and the rolling shutter effect. In this paper, we present a dense 3D reconstruction method from small motion clips using commercial hand-held cameras, which typically cause the undesired rolling shutter artifact. To address these problems, we introduce a novel small motion bundle adjustment that effectively compensates for the rolling shutter effect. Moreover, we propose a pipeline for a fine-scale dense 3D reconstruction that models the rolling shutter effect by utilizing both sparse 3D points and the camera trajectory from narrow-baseline images. In this reconstruction, the sparse 3D points are propagated to obtain an initial depth hypothesis using a geometry guidance term. Then, the depth information on each pixel is obtained by sweeping the plane around each depth search space near the hypothesis. The proposed framework shows accurate dense reconstruction results suitable for various sought-after applications. Both qualitative and quantitative evaluations show that our method consistently generates better depth maps compared to state-of-the-art methods. [ABSTRACT FROM AUTHOR]
- Published
- 2019
- Full Text
- View/download PDF
49. Column Distances of Convolutional Codes Over ${\mathbb Z}_{p^r}$.
- Author
-
Napp, Diego, Pinto, Raquel, and Toste, Marisa
- Subjects
- *
ERROR-correcting codes , *COLUMN foundations , *GEOMETRIC vertices , *SINGLETON bounds , *CYCLIC codes - Abstract
Maximum distance profile codes over finite non-binary fields have been introduced and thoroughly studied in the last decade. These codes have the property that their column distances are maximal among all codes of the same rate and degree. In this paper, we aim at studying this fundamental concept in the context of convolutional codes over a finite ring. We extensively use the concept of $p$ -encoder to establish the theoretical framework and derive several bounds on the column distances. In particular, a method for constructing (not necessarily free) maximum distance profile convolutional codes over ${\mathbb Z}_{p^{r}}$ is presented. [ABSTRACT FROM AUTHOR]
- Published
- 2019
- Full Text
- View/download PDF
50. Computationally Efficient Off-Line Joint Change Point Detection in Multiple Time Series.
- Author
-
Eriksson, Markus and Olofsson, Tomas
- Subjects
- *
CHANGE-point problems , *COMPUTATIONAL complexity , *ALGORITHMS , *BAYESIAN analysis , *TIME series analysis , *ARTIFICIAL intelligence - Abstract
In this paper, a computationally efficient algorithm for Bayesian joint change point detection (CPD) in multiple time series is presented. The data generation model includes a number of change configurations (CC), each affecting a unique subset of the time series, which introduces correlation between the positions of change points (CPs) in the monitored time series. The inference objective is to identify joint changes and the associated CC. The algorithm consists of two stages: First, a univariate CPD algorithm is applied separately to each of the involved time series. The outcomes of this step are maximum a posteriori (MAP) detected CPs and posterior distributions of CPs conditioned on the MAP CPs. These outcomes are used in combination to approximate the posterior for the CCs. In the second algorithm stage, dynamic programming is used to find the maxima of this approximate CC posterior. The algorithm is applied to synthetic data, and it is shown to be both significantly faster and more accurate compared to a previously proposed algorithm designed to solve similar problems. Also, the initial algorithm is extended with steps from the maximization–maximization algorithm, which allows the hyperparameters of the data generation model to be estimated jointly with the CCs, and we show that these estimates coincide with estimates obtained from a Markov chain Monte Carlo algorithm. [ABSTRACT FROM AUTHOR]
- Published
- 2019
- Full Text
- View/download PDF
Discovery Service for Jio Institute Digital Library
For full access to our library's resources, please sign in.