检索结果-内蒙古大学图书馆

Construction of Bio-constrained code for DNA Data Storage

IEEE COMMUNICATIONS LETTERS 2019年第6期23卷 963-966页

作者： Wang, Yixin Noor-A-Rahim, Md Gunawan, Erry Guan, Yong Liang Poh, Chueh Loo Nanyang Technol Univ Sch Elect & Elect Engn Singapore 639798 Singapore Univ Coll Cork Sch Comp Sci & IT Cork T12 K8AF Ireland Natl Univ Singapore Dept Biomed Engn Singapore 119077 Singapore

With extremely high density and durable preservation, DNA data storage has become one of the most cutting-edge techniques for long-term data storage. Similar to traditional storage which impose restrictions on the form of encoded data, data stored in DNA storage systems are also subject to two biochemical constraints, i.e., maximum homopolymer run limit and balanced GC content limit. Previous studies used successive process to satisfy these two constraints. As a result, the process suffers low efficiency and high complexity. In this letter, we propose a novel content-balanced run-length limited code with an efficient code construction method, which generates short DNA sequences that satisfy both constraints at one time. Besides, we develop an encoding method to map binary data into long DNA sequences for DNA data storage, which ensures both local and global stability in terms of satisfying the biochemical constraints. The proposed encoding method has high effective code rate of 1.917 bits per nucleotide and low coding complexity.

关键词： DNA data storage constrained code run-length limited code long term data storage

来源：评论

学校读者我要写书评

暂无评论

Efficient Encoding of Binary Constant-Weight codes: Variable-Length Balancing Schemes a La Knuth

引用

IEEE TRANSACTIONS ON INFORMATION THEORY 2024年第7期70卷 4731-4746页

作者： Dao, Duc Tu Kiah, Han Mao Nguyen, Tuan Thanh Nanyang Technol Univ Sch Phys & Math Sci Singapore 637371 Singapore Singapore Univ Technol & Design Sci Math & Technol Cluster Singapore 487372 Singapore

We study and propose schemes that map messages onto constant-weight codewords using variable-length prefixes. We provide polynomial-time computable formulas that estimate the average number of redundant bits incurred by our schemes. In addition to the exact formulas, we also perform an asymptotic analysis and demonstrate that our scheme uses 1/2 log(2) n + O(1) redundant bits to encode messages into length- n words with weight $(n/2)+ mu for constant mu . We also propose schemes that map messages into balanced codebooks with error-correcting capabilities. For such schemes, we provide methods to enumerate the average number of redundant bits.

关键词： Redundancy codes Encoding DNA Memory Transforms Surveys Balanced code constant-weight code constrained code encoding

来源：评论

学校读者我要写书评

暂无评论

Minimally Modified Balanced codes

引用

IEEE TRANSACTIONS ON INFORMATION THEORY 2023年第1期69卷 187-193页

作者： Immink, Kees A. Schouhamer A. Weber, Jos H. Turing Machines Inc NL-3016 DK Rotterdam Netherlands Delft Univ Technol Dept Appl Math NL-2628 CD Delft Netherlands

We present and analyze a new construction of bipolar balanced codes where each codeword contains equally many -1's and +1's. The new code is minimally modified as the number of symbol changes made to the source word for translating it into a balanced codeword is as small as possible. The balanced codes feature low redundancy and time complexity. Large look-up tables are avoided.

关键词： Balanced code constrained code error propagation Raney's Lemma

来源：评论

学校读者我要写书评

暂无评论

Asymptotic Behavior and Typicality Properties of Runlength-Limited Sequences

引用

IEEE TRANSACTIONS ON INFORMATION THEORY 2022年第3期68卷 1638-1650页

作者： Kovacevic, Mladen Vukobratovic, Dejan Univ Novi Sad Fac Tech Sci Novi Sad 21000 Serbia

This paper studies properties of binary runlength-limited sequences with additional constraints on their Hamming weight and/or their number of runs of identical symbols. An algebraic and a probabilistic (entropic) characterization of the exponential growth rate of the number of such sequences, i.e., their information capacity, are obtained by using the methods of multivariate analytic combinatorics, and properties of the capacity as a function of its parameters are stated. The second-order term in the asymptotic expansion of the rate of these sequences is also given, and the typical values of the relevant quantities are derived. Several applications of the results are illustrated, including bounds on codes for weight-preserving and run-preserving channels (e.g., the run-preserving insertion-deletion channel), a sphere-packing bound for channels with sparse error patterns, and the asymptotics of constant-weight sub-block constrained sequences. In addition, the asymptotics of a closely related notion-q-ary sequences with fixed Manhattan weight-is briefly discussed, and an application in coding for molecular timing channels is illustrated.

关键词： codes Encoding Hamming weight Probabilistic logic Upper bound Technological innovation Synchronization constrained code constrained sequences RLL sequences constant-weight code asymptotic rate typical sequences insertion deletion weight-preserving channel timing channel Manhattan weight analytic combinatorics

来源：评论

学校读者我要写书评

暂无评论

A New Detection Method for Noisy Channels With Time-Varying Offset

引用

IEEE TRANSACTIONS ON INFORMATION THEORY 2022年第5期68卷 3108-3114页

作者： Immink, Kees A. Schouhamer Weber, Jos H. Turing Machines Inc NL-3016 DK Rotterdam Netherlands Delft Univ Technol Dept Appl Math NL-2628 Delft Netherlands

We consider noisy communications and storage systems that are hampered by varying offset of unknown magnitude such as low-frequency signals of unknown amplitude added to the sent signal. We study and analyze a new detection method whose error performance is independent of both unknown base offset and offset's slew rate. The new method requires, for a codeword length n >= 12, less than 1.5 dB more noise margin than Euclidean distance detection. The relationship with constrained codes based on mass-centered codewords and the new detection method is discussed.

关键词： Channel mismatch constrained code Pearson code Pearson distance slew rate varying offset

来源：评论

学校读者我要写书评

暂无评论

On the Maximum Number of Non-Confusable Strings Evolving under Short Tandem Duplications

引用

PROBLEMS OF INFORMATION TRANSMISSION 2022年第2期58卷 111-121页

作者： Kovacevic, M. Univ Novi Sad Fac Tech Sci Novi Sad Serbia

The set of all q-ary strings that do not contain repeated substrings of length <= 3 (i.e., that do not contain substrings of the form aa, abab, and abcabc) constitutes a code correcting an arbitrary number of tandem-duplication mutations of length <= 3. In other words, any two such strings are non-confusable in the sense that they cannot produce the same string while evolving under tandem duplications of length <= 3. We demonstrate that this code is asymptotically optimal in terms of rate, meaning that it represents the largest set of non-confusable strings up to subexponential factors. This result settles the zero-error capacity problem for the last remaining case of tandem-duplication channels satisfying the "root-uniqueness" property.

关键词： tandem duplication tandem repeat duplication error repetition error sticky insertion DNA storage error correction zero-error capacity constrained code square-free string

来源：评论

学校读者我要写书评

暂无评论

Skip-Slidin Window codes

引用

IEEE TRANSACTIONS ON COMMUNICATIONS 2021年第5期69卷 2824-2836页

作者： Wu, Ting-Yi Tandon, Anshoo Varshney, Lav R. Motani, Mehul Sun Yat Sen Univ Sch Elect & Commun Engn Guangzhou 510275 Peoples R China Natl Univ Singapore Dept Elect & Comp Engn Singapore 117583 Singapore Univ Illinois Coordinated Sci Lab Urbana IL 61801 USA Univ Illinois Dept Elect & Comp Engn Urbana IL 61801 USA

constrained coding is used widely in digital communication and storage systems. In this article, we study a generalized sliding window constraint called the skip-sliding window. A skip-sliding window (SSW) code is defined in terms of the length L of a sliding window, skip length J, and cost constraint E in each sliding window. Each valid codeword of length L kJ is determined by k + 1 windows of length L where window i starts at (iJ + 1)th symbol for all non-negative integers i such that i <= k;and the cost constraint E in each window must be satisfied. SSW coding constraints naturally arise in applications such as simultaneous energy and information transfer, and SSW codes are also potential candidates for visible light communications. In this work, two methods are given to enumerate the size of SSW codes and further refinements are made to reduce the enumeration complexity. Using the proposed enumeration methods, the noiseless capacity of binary SSW codes is determined and some useful observations are made, such as the fact that SSW codes provide greater capacity than certain related classes of constrained codes. Moreover, we provide noisy capacity bounds for SSW codes.

关键词： Skip-sliding window constrained code Goulden-Jackson cluster method capacity

来源：评论

学校读者我要写书评

暂无评论

Efficient Encoding of constrained Block codes

引用

IEEE COMMUNICATIONS LETTERS 2021年第11期25卷 3468-3472页

作者： Immink, Kees A. Schouhamer Cai, Kui Turing Machines Inc NL-3016 DK Rotterdam Netherlands Singapore Univ Technol & Design SUTD Sci Math & Technol Cluster Singapore 487372 Singapore

We present coding methods for generating l-symbol constrained codewords taken from a set, S, of allowed codewords. In standard practice, the size of the set S, denoted by M = vertical bar S vertical bar, is truncated to an integer power of two, which may lead to a serious waste of capacity. We present an efficient and low-complexity coding method for avoiding the truncation loss, where the encoding is accomplished in two steps: first, a series of binary input (user) data is translated into a series of M-ary symbols in the alphabet M = {0,..., M - 1}. Then, in the second step, the M-ary symbols are translated into a series of admissible l-symbol words in S by using a small look-up table. The presented construction of Pearson codes and fixed-weight codes offers a rate close to capacity. For example, a 255B320B balanced code, where 255 source bits are translated into 32 10-bit balanced codewords, has a rate 0.1% below capacity.

关键词： constrained code code design binary block code balanced code Pearson code

来源：评论

学校读者我要写书评

暂无评论

Block codes for Energy-Harvesting Sliding-Window constrained Channels

引用

IEEE COMMUNICATIONS LETTERS 2020年第11期24卷 2383-2386页

作者： Schouhamer Immink, Kees A. Kui, Cai Turing Machines Inc NL-3016 DK Rotterdam Netherlands Singapore Univ Technol & Design SUTD Sci Math & Technol Cluster Singapore 487372 Singapore

Energy-harvesting sliding-window constrained block codes guarantee that within any prescribed window of l consecutive bits the constrained sequence has at least t, t >= 1, 1's. Prior art code design methods build upon the finite-state machine description of the (l, t) constraint, but as the number of states equals l choose t, a code design becomes prohibitively complex for mounting l and t. We present a new block code construction that circumvents the enumeration of codewords using a finite-state description of the (l, t)-constraint. The codewords of the block code are encoded and decoded using a single look-up table. For (l = 4, t = 2), the new block codes are maximal, that is, they have the largest possible number of codewords for its parameters.

关键词： Block codes Art Table lookup Windows Internet of Things Systematics Energy harvesting sliding-window constrained code constrained code code design binary block code code construction

来源：评论

学校读者我要写书评

暂无评论

Runlength-Limited Sequences and Shift-Correcting codes: Asymptotic Analysis

引用

IEEE TRANSACTIONS ON INFORMATION THEORY 2019年第8期65卷 4804-4814页

作者： Kovacevic, Mladen Natl Univ Singapore Dept Elect & Comp Engn Singapore 117583 Singapore Univ Novi Sad BioSense Inst Novi Sad 21000 Serbia

This work is motivated by the problem of error correction in bit-shift channels with the so-called (d, k) input constraints (where successive 1' s are required to be separated by at least d and at most k zeros, 0 <= d < k <= infinity). Bounds on the size of optimal (d, k)-constrained codes correcting a fixed number of bit-shifts are derived, with a focus on their asymptotic behavior in the large block-length limit. The upper bound is obtained by a packing argument, while the lower bound follows from a construction based on a family of integer lattices. Several properties of (d, k)-constrained sequences that may be of independent interest are established as well;in particular, the exponential growth rate of the number of (d, k)-constrained constant-weight sequences is characterized. The results are relevant for magnetic and optical information storage systems, reader-to-tag RFID channels, and other communication models where bit-shift errors are dominant and where (d, k)-constrained sequences are used for modulation.

关键词： Runlength-limited sequence constrained code constant-weight code bit-shift channel peak shift timing error integer composition Manhattan metric asymmetric distance

来源：评论

学校读者我要写书评

暂无评论

建议与咨询留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

建议与咨询 留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案： 新增检索档案 确定 取消

请选择收藏分类： 新增自定义分类 确定 取消

通借通还

建议与咨询留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

请选择保存的检索档案：

请选择收藏分类：