Source author record

Kenji Yasunaga

Explore this author’s publications, collaborators and research topics. This catalog record has not been claimed by its author.

ResearcherUnclaimed source record

Information Theory math.IT

Catalog footprint

Research overview

2works

2topics

2close collaborators

Actions

Is this your work?

Open graph Browse papers

preprint2020arXiv

On the List Decodability of Insertions and Deletions

In this work, we study the problem of list decoding of insertions and deletions. We present a Johnson-type upper bound on the maximum list size. The bound is meaningful only when insertions occur. Our bound implies that there are binary codes of rate $Ω(1)$ that are list-decodable from a $0.707$ -fraction of insertions. For any $τ_\mathsf{I} \geq 0$ and $τ_\mathsf{D} \in [0,1)$ , there exist $q$ -ary codes of rate $Ω(1)$ that are list-decodable from a $τ_\mathsf{I}$ -fraction of insertions and $τ_\mathsf{D}$ -fraction of deletions, where $q$ depends only on $τ_\mathsf{I}$ and $τ_\mathsf{D}$ . We also provide efficient encoding and decoding algorithms for list-decoding from $τ_\mathsf{I}$ -fraction of insertions and $τ_\mathsf{D}$ -fraction of deletions for any $τ_\mathsf{I} \geq 0$ and $τ_\mathsf{D} \in [0,1)$ . Based on the Johnson-type bound, we derive a Plotkin-type upper bound on the code size in the Levenshtein metric.

preprint2005arXiv

Relations between the Local Weight Distributions of a Linear Block Code, Its Extended Code, and Its Even Weight Subcode

Relations between the local weight distributions of a binary linear code, its extended code, and its even weight subcode are presented. In particular, for a code of which the extended code is transitive invariant and contains only codewords with weight multiples of four, the local weight distribution can be obtained from that of the extended code. Using the relations, the local weight distributions of the $(127,k)$ primitive BCH codes for $k\leq50$ , the $(127,64)$ punctured third-order Reed-Muller, and their even weight subcodes are obtained from the local weight distribution of the $(128,k)$ extended primitive BCH codes for $k\leq50$ and the $(128,64)$ third-order Reed-Muller code. We also show an approach to improve an algorithm for computing the local weight distribution proposed before.

Inspect adjacent papers, topics, institutions and collaborators without losing the researcher page.

Building this map preview

BZPEER is loading the nearby papers, people, topics and institutions for this page.