English (United Kingdom)

https://curated-unify.zendy.io/wp-json/zendy-region/v1/featured_content/oa?rat=en

https://curated-unify.zendy.io/wp-json/zendy-region/v1/highlighted_journal/

Global: Zendy Plus annual

Presents the access of premium content as premium feature

Premium Content

Presents the keyphrase highlighting as premium feature

Keyphrase Highlighting

Presents the summarisation as premium feature

Summarisation

Insights

Presents the pdf analysis as premium feature

PDF Analysis

Presents the zaia usage as premium feature

ZAIA

Global: Zendy Plus monthly

Global: Zendy Tools annual

Global: Zendy Tools monthly

Global: Zendy Free Plan

This paper tackles two problems that are relevant to coding for insertionsand deletions. These problems are motivated by several applications, among themis reconstructing strands in DNA-based storage systems. Under this paradigm, aword is transmitted over some fixed number of identical independent channelsand the goal of the decoder is to output the transmitted word or some closeapproximation of it. The first part of this paper studies the deletion channelthat deletes a symbol with some fixed probability $p$, while focusing on twoinstances of this channel. Since operating the maximum likelihood (ML) decoderin this case is computationally unfeasible, we study a slightly degradedversion of this decoder for two channels and its expected normalized distance.We identify the dominant error patterns and based on these observations, it isderived that the expected normalized distance of the degraded ML decoder isroughly $\frac{3q-1}{q-1}p^2$, when the transmitted word is any $q$-arysequence and $p$ is the channel's deletion probability. We also study the caseswhen the transmitted word belongs to the Varshamov Tenengolts (VT) code or theshifted VT code. Additionally, the insertion channel is studied as well as thecase of two insertion channels. These theoretical results are verified bycorresponding simulations. The second part of the paper studies optimaldecoding for a special case of the deletion channel, the $k$-deletion channel,which deletes exactly $k$ symbols of the transmitted word uniformly at random.In this part, the goal is to understand how an optimal decoder operates inorder to minimize the expected normalized distance. A full characterization ofan efficient optimal decoder for this setup, referred to as the maximumlikelihood* (ML*) decoder, is given for a channel that deletes one or twosymbols.

On The Decoding Error Weight of One or Two Deletion Channels