اشترك بالحزمة الذهبية واحصل على وصول غير محدود شمرا أكاديميا
تسجيل مستخدم جديدAlgorithms for reconstruction over single and multiple deletion channels
73
0
0.0
(
0
)
نشر من قبل
Sundara Rajan Srinivasavaradhan
تاريخ النشر
2020
مجال البحث
الهندسة المعلوماتية
والبحث باللغة
English
اسأل ChatGPT حول البحث
ﻻ يوجد ملخص باللغة العربية
Recent advances in DNA sequencing technology and DNA storage systems have rekindled the interest in deletion channels. Multiple recent works have looked at variants of sequence reconstruction over a single and over multiple deletion channels, a notoriously difficult problem due to its highly combinatorial nature. Although works in theoretical computer science have provided algorithms which guarantee perfect reconstruction with multiple independent observations from the deletion channel, they are only applicable in the large blocklength regime and more restrictively, when the number of observations is also large. Indeed, with only a few observations, perfect reconstruction of the input sequence may not even be possible in most cases. In such situations, maximum likelihood (ML) and maximum aposteriori (MAP) estimates for the deletion channels are natural questions that arise and these have remained open to the best of our knowledge. In this work, we take steps to answer the two aforementioned questions. Specifically: 1. We show that solving for the ML estimate over the single deletion channel (which can be cast as a discrete optimization problem) is equivalent to solving its relaxation, a continuous optimization problem; 2. We exactly compute the symbolwise posterior distributions (under some assumptions on the priors) for both the single as well as multiple deletion channels. As part of our contributions, we also introduce tools to visualize and analyze error events, which we believe could be useful in other related problems concerning deletion channels.
قيم البحث
اقرأ أيضاً
This paper investigates the problem of correcting multiple criss-cross insertions and deletions in arrays. More precisely, we study the unique recovery of $n times n$ arrays affected by $t$-criss-cross deletions defined as any combination of $t_r$ ro
w and $t_c$ column deletions such that $t_r + t_c = t$ for a given $t$. We show an equivalence between correcting $t$-criss-cross deletions and $t$-criss-cross insertions and show that a code correcting $t$-criss-cross insertions/deletions has redundancy at least $tn + t log n - log(t!)$. Then, we present an existential construction of $t$-criss-cross insertion/deletion correcting code with redundancy bounded from above by $tn + mathcal{O}(t^2 log^2 n)$. The main ingredients of the presented code construction are systematic binary $t$-deletion correcting codes and Gabidulin codes. The first ingredient helps locating the indices of the inserted/deleted rows and columns, thus transforming the insertion/deletion-correction problem into a row/column erasure-correction problem which is then solved using the second ingredient.
Several channels with asynchronous side information are introduced. We first consider single-user state-dependent channels with asynchronous side information at the transmitter. It is assumed that the state information sequence is a possibly delayed
version of the state sequence, and that the encoder and the decoder are aware of the fact that the state information might be delayed. It is additionally assumed that an upper bound on the delay is known to both encoder and decoder, but other than that, they are ignorant of the actual delay. We consider both the causal and the noncausal cases and present achievable rates for these channels, and the corresponding coding schemes. We find the capacity of the asynchronous Gelfand-Pinsker channel with feedback. Finally, we consider a memoryless state dependent channel with asynchronous side information at both the transmitter and receiver, and establish a single-letter expression for its capacity.
This paper considers state estimation of linear systems using analog amplify and forwarding with multiple sensors, for both multiple access and orthogonal access schemes. Optimal state estimation can be achieved at the fusion center using a time vary
ing Kalman filter. We show that in many situations, the estimation error covariance decays at a rate of $1/M$ when the number of sensors $M$ is large. We consider optimal allocation of transmission powers that 1) minimizes the sum power usage subject to an error covariance constraint and 2) minimizes the error covariance subject to a sum power constraint. In the case of fading channels with channel state information the optimization problems are solved using a greedy approach, while for fading channels without channel state information but with channel statistics available a sub-optimal linear estimator is derived.
We consider quantum channels with two senders and one receiver. For an arbitrary such channel, we give multi-letter characterizations of two different two-dimensional capacity regions. The first region characterizes the rates at which it is possible
for one sender to send classical information while the other sends quantum information. The second region gives the rates at which each sender can send quantum information. We give an example of a channel for which each region has a single-letter description, concluding with a characterization of the rates at which each user can simultaneously send classical and quantum information.
In this paper we use a variation of simulated annealing algorithm for optimizing two-dimensional constellations with 32 signals. The main objective is to maximize the symmetric pragmatic capacity under the peak-power constraint. The method allows the
joint optimization of constellation and binary labeling. We also investigate the performance of the optimized constellation over nonlinear satellite channel under additive white Gaussian noise. We consider the performance over systems with and without pre-distorters. In both cases the optimized constellations perform considerably better than the conventional Amplitude Phase Shift Keying (APSK) modulations, used in the current digital video broadcasting standard (DVB-S2) on satellite channels. Based on our optimized constellations, we also propose a new labeling for the 4+12+16-APSK constellation of the DVB-S2 standard which is Gray over all rings.
سجل دخول لتتمكن من نشر تعليقات
التعليقات
جاري جلب التعليقات
سجل دخول لتتمكن من متابعة معايير البحث التي قمت باختيارها
