Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userDistributed Arithmetic Coding for Sources with Hidden Markov Correlation
88
0
0.0
(
0
)
Added by
Yong Fang
Publication date
2021
fields
Informatics Engineering
and research's language is
English
Ask ChatGPT about the research
No Arabic abstract
Distributed arithmetic coding (DAC) has been shown to be effective for Slepian-Wolf coding, especially for short data blocks. In this letter, we propose to use the DAC to compress momery-correlated sources. More specifically, the correlation between sources is modeled as a hidden Markov process. Experimental results show that the performance is close to the theoretical Slepian-Wolf limit.
rate research
Read More
Consider the set of source distributions within a fixed maximum relative entropy with respect to a given nominal distribution. Lossless source coding over this relative entropy ball can be approached in more than one way. A problem previously considered is finding a minimax average length source code. The minimizing players are the codeword lengths --- real numbers for arithmetic codes, integers for prefix codes --- while the maximizing players are the uncertain source distributions. Another traditional minimizing objective is the first one considered here, maximum (average) redundancy. This problem reduces to an extension of an exponential Huffman objective treated in the literature but heretofore without direct practical application. In addition to these, this paper examines the related problem of maximal minimax pointwise redundancy and the problem considered by Gawrychowski and Gagie, which, for a sufficiently small relative entropy ball, is equivalent to minimax redundancy. One can consider both Shannon-like coding based on optimal real number (ideal) codeword lengths and a Huffman-like optimal prefix coding.
This paper focuses on the structural properties of test channels, of Wyners operational information rate distortion function (RDF), $overline{R}(Delta_X)$, of a tuple of multivariate correlated, jointly independent and identically distributed Gaussian random variables (RVs), ${X_t, Y_t}_{t=1}^infty$, $X_t: Omega rightarrow {mathbb R}^{n_x}$, $Y_t: Omega rightarrow {mathbb R}^{n_y}$, with average mean-square error at the decoder, $frac{1}{n} {bf E}sum_{t=1}^n||X_t - widehat{X}_t||^2leq Delta_X$, when ${Y_t}_{t=1}^infty$ is the side information available to the decoder only. We construct optimal test channel realizations, which achieve the informational RDF, $overline{R}(Delta_X) triangleqinf_{{cal M}(Delta_X)} I(X;Z|Y)$, where ${cal M}(Delta_X)$ is the set of auxiliary RVs $Z$ such that, ${bf P}_{Z|X,Y}={bf P}_{Z|X}$, $widehat{X}=f(Y,Z)$, and ${bf E}{||X-widehat{X}||^2}leq Delta_X$. We show the fundamental structural properties: (1) Optimal test channel realizations that achieve the RDF, $overline{R}(Delta_X)$, satisfy conditional independence, $ {bf P}_{X|widehat{X}, Y, Z}={bf P}_{X|widehat{X},Y}={bf P}_{X|widehat{X}}, hspace{.2in} {bf E}Big{XBig|widehat{X}, Y, ZBig}={bf E}Big{XBig|widehat{X}Big}=widehat{X} $ and (2) similarly for the conditional RDF, ${R}_{X|Y}(Delta_X) triangleq inf_{{bf P}_{widehat{X}|X,Y}:{bf E}{||X-widehat{X}||^2} leq Delta_X} I(X; widehat{X}|Y)$, when ${Y_t}_{t=1}^infty$ is available to both the encoder and decoder, and the equality $overline{R}(Delta_X)={R}_{X|Y}(Delta_X)$.
In a distributed storage system, code symbols are dispersed across space in nodes or storage units as opposed to time. In settings such as that of a large data center, an important consideration is the efficient repair of a failed node. Efficient repair calls for erasure codes that in the face of node failure, are efficient in terms of minimizing the amount of repair data transferred over the network, the amount of data accessed at a helper node as well as the number of helper nodes contacted. Coding theory has evolved to handle these challenges by introducing two new classes of erasure codes, namely regenerating codes and locally recoverable codes as well as by coming up with novel ways to repair the ubiquitous Reed-Solomon code. This survey provides an overview of the efforts in this direction that have taken place over the past decade.
In large scale distributed storage systems (DSS) deployed in cloud computing, correlated failures resulting in simultaneous failure (or, unavailability) of blocks of nodes are common. In such scenarios, the stored data or a content of a failed node can only be reconstructed from the available live nodes belonging to the available blocks. To analyze the resilience of the system against such block failures, this work introduces the framework of Block Failure Resilient (BFR) codes, wherein the data (e.g., a file in DSS) can be decoded by reading out from a same number of codeword symbols (nodes) from a subset of available blocks of the underlying codeword. Further, repairable BFR codes are introduced, wherein any codeword symbol in a failed block can be repaired by contacting a subset of remaining blocks in the system. File size bounds for repairable BFR codes are derived, and the trade-off between per node storage and repair bandwidth is analyzed, and the corresponding minimum storage regenerating (BFR-MSR) and minimum bandwidth regenerating (BFR-MBR) points are derived. Explicit codes achieving the two operating points for a special case of parameters are constructed, wherein the underlying regenerating codewords are distributed to BFR codeword symbols according to combinatorial designs. Finally, BFR locally repairable codes (BFR-LRC) are introduced, an upper bound on the resilience is derived and optimal code construction are provided by a concatenation of Gabidulin and MDS codes. Repair efficiency of BFR-LRC is further studied via the use of BFR-MSR/MBR codes as local codes. Code constructions achieving optimal resilience for BFR-MSR/MBR-LRCs are provided for certain parameter regimes. Overall, this work introduces the framework of block failures along with optimal code constructions, and the study of architecture-aware coding for distributed storage systems.
While two hidden Markov process (HMP) resp. quantum random walk (QRW) parametrizations can differ from one another, the stochastic processes arising from them can be equivalent. Here a polynomial-time algorithm is presented which can determine equivalence of two HMP parametrizations $cM_1,cM_2$ resp. two QRW parametrizations $cQ_1,cQ_2$ in time $O(|S|max(N_1,N_2)^{4})$, where $N_1,N_2$ are the number of hidden states in $cM_1,cM_2$ resp. the dimension of the state spaces associated with $cQ_1,cQ_2$, and $S$ is the set of output symbols. Previously available algorithms for testing equivalence of HMPs were exponential in the number of hidden states. In case of QRWs, algorithms for testing equivalence had not yet been presented. The core subroutines of this algorithm can also be used to efficiently test hidden Markov processes and quantum random walks for ergodicity.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
