scientific article; zbMATH DE number 3240929
Untersuchungen über die Übertragung binärer Information legen gewöhnlich einen Kanal zugrunde, bei dem als Fehler nur Umkehrungen, also Verfälschungen des Zeichens \(0\) in \(1\) bzw. \(1\) in \(0\) auftreten können. Die vorliegende Arbeit betrachtet dagegen Kanäle, bei denen als Fehler auch Auslöschungen und Einfügungen vorkommen können, wo also das Zeichen \(0\) oder \(1\) in das Leerzeichen bzw. das Leerzeichen in eines der Zeichen \(0\) oder \(1\) verfälscht werden kann. Das Ziel dieser Untersuchung ist die Konstruktion optimaler Binärcodes, mit denen sowohl Umkehrungen als auch Auslöschungen und Einfügungen korrigiert werden können. Zunächst werden Codes betrachtet, welche nur für aus Auslöschungen und Einfügungen bestehende Fehler korrigierbar sind. Dabei zeigt sich, daß beide Fehlerarten bezüglich ihrer Korrigierbarkeit äquivalent sind. In Analogie zum Hamming-Abstand zweier Codewörter definiert der Verf. bezüglich dieser Fehlerarten eine metrische Abstandsfunktion, mit deren Hilfe sich eine Bedingung dafür angeben läßt, daß ein Code der Länge \(n\) für \(s\) oder weniger Fehler korrigierbar ist. Sodann werden für \(n\rightarrow \infty\) obere und untere Schranken für die Anzahl der Wörter eines optimalen Binärcodes abgeleitet, mit dem bis zu \(s\) Fehler korrigiert werden können. Im zweiten Teil der Arbeit werden die gewonnenen Ergebnisse verallgemeinert auf Codes für Kanäle, in denen nun Auslöschungen, Einfügungen und auch Umkehrungen als Fehler auftreten können. Auch dafür werden mittels einer Abstandsfunktion eine Bedingung für die Korrigierbarkeit von \(s\) oder weniger Fehlern angegeben und Schranken für die Anzahl der Wörter eines optimalen Binärcodes abgeleitet. Der letzte Teil der Untersuchung schließlich beschäftigt sich mit dem Problem, das mit Fehlern der drei angegebenen Arten behaftete Empfangsergebnis einer Folge von \(n\)-stelligen Binärwörtern wieder in die ursprüngliche Folge der gesendeten Wörter zu decodieren, wenn der Übertragungskanal so beschaffen ist, daß auf ein Segment von \(n\) Zeichen nicht mehr als \(s\) Fehler treffen. Ein Code wird für einen derartigen Kanal \glqq zulässig\grqq{} genannt, wenn eine im weitesten Sinne automatische Vorrichtung existiert, mit der in endlich vielen Schritten die Abbildung der empfangenen Folge auf die gesendete Folge bewerkstelligt werden kann. Der Verf. betrachtet hier vier Kanaltypen, die sich durch verschiedene Kombinationen der drei vorkommenden Fehlerarten beschreiben lassen, und gibt für jeden sowohl Bedingungen für die Zulässigkeit eines Codes als auch Vorschläge für die Konstruktion derartiger Binärcodes an.
- Solving similarity joins and range queries in metric spaces with the list of twin clusters
- Topology on words
- Error graphs and the reconstruction of elements in groups
- On the longest common parameterized subsequence
- An almost-linear time and linear space algorithm for the longest common subsequence problem
- An integer linear programming approach for approximate string comparison
- Constrained string editing
- Data structures and algorithms for approximate string matching
- Efficient regular grammatical inference techniques by the use of partial similarities and their logical relationships
- Approximate string-matching with q-grams and maximal matches
- String editing under a combination of constraints
- Using Hirschberg's algorithm to generate random alignments of strings
- Constrained many-to-one string editing with memory
- Block edit models for approximate string matching
- Web mining with relational clustering
- Overlap matching.
- Spectral embedding of graphs.
- Error-detecting properties of languages
- A fast and practical bit-vector algorithm for the longest common subsequence problem
- A re-characterization of the Kemeny distance
- \(\mathrm{PSOM}^2\) -- partitioning-based scalable ontology matching using MapReduce
- Unweighted linear congruences with distinct coordinates and the Varshamov-Tenengolts codes
- Quantitative monitoring of STL with edit distance
- Approximation of graph edit distance based on Hausdorff matching
- Mathematics and flamenco: an unexpected partnership
- Period recovery of strings over the Hamming and edit distances
- Efficient algorithms for computing the inner edit distance of a regular language via transducers
- On measuring similarity for sequences of itemsets
- Detecting life signatures with RNA sequence similarity measures
- Duplication-correcting codes
- siEDM: an efficient string index and search algorithm for edit distance with moves
- On searching and indexing sequences of temporal intervals
- Tandem cyclic alignment
- Triangular covers of a digital object
- A universal bound for a covering in regular posets and its application to pool testing
- Comparison of strings belonging to the same family
- Approximate swapped matching.
- Edit distance of run-length encoded strings.
- How hard is computing the edit distance?
- An algebra of discrete channels that involve combinations of three basic error types
- A new dissimilarity measure for comparing labeled graphs
- Good edit similarity learning by loss minimization
- String matching with up to k swaps and mismatches
- Bayesian instance selection for the nearest neighbor rule
- Fifty years of graph matching, network alignment and network comparison
- Calibrating AdaBoost for phoneme classification
- Diversity metrics for direct-coded variable-length chromosome shortest path problem evolutionary algorithms
- On 2-dimensional insertion-deletion Reed-Solomon codes with optimal asymptotic error-correcting capability
- Consensus string problem for multiple regular languages
- Feedback insertion-deletion codes
- How to choose a fair delegation?
- Real-time error correction codes for deletable errors
- Variable-length codes independent or closed with respect to edit relations
- Decoding algorithms of monotone codes and azinv codes and their unified view
- Exploiting pseudo-locality of interchange distance
- Transformer-based deep neural language modeling for construct-specific automatic item generation
- The Modular Subset-Sum Problem and the size of deletion correcting codes
- Fast similarity search for graphs by edit distance
- A number theoretic formula and asymptotic optimality of cardinalities of BAD correcting codes
- Unstructured network topology begets order-based representation by privileged neurons
- Applications of Gaussian binomials to coding theory for deletion error correction
- Surprises in approximating Levenshtein distances
- Deletion correcting codes meet the Littlewood-Offord problem
- Construction of single-deletion-correcting DNA codes using CIS codes
- A gift with thoughtfulness: a field experiment on work incentives
- Estimating sequence similarity from read sets for clustering next-generation sequencing data
- Mining relaxed functional dependencies from data
- Latent feature extraction for process data via multidimensional scaling
- Fast robust optimization using bias correction applied to the mean model
- DNA codes for nonadditive stem similarity
- Error-repair parsing schemata
- Distance measures for biological sequences: some recent approaches
- A generalized correlation attack on a class of stream ciphers based on the Levenshtein distance
- Fast parallel and serial multidimensional approximate array matching
- Mathematical properties of soft cardinality: enhancing Jaccard, Dice and cosine similarity measures with element-wise distance
- Metrization of the T-alphabet: measuring the distance between multidimensional real discrete sequences
- Knowing-how under uncertainty
- On bilateral matching between fuzzy sets
- Optimal string clustering based on a Laplace-like mixture and EM algorithm on a set of strings
- Global and local sequence alignment with a bounded number of gaps
- Adaptive degraded document image binarization
- Algorithms for subsequence combinatorics
- Edit distance for a run-length-encoded string and an uncompressed string
- Computing the edit distance of a regular language
- Weighted approximate parameterized string matching
- Extending alignments with k-mismatches and -gaps
- The graph matching problem
- Balanced compact clustering for efficient range queries in metric spaces
- Languages with mismatches
- Moving coins
- Fuzzy automata with -moves compute fuzzy measures between strings
- An efficient approach for the rank aggregation problem
- Fast algorithm and implementation of dissimilarity self-organizing maps
- Bit-parallel approximate string matching algorithms with transposition
- Approximate matching between a context-free grammar and a finite-state automaton
- Fuzzy clustering of mixed data
- On matching of intuitionistic fuzzy sets
- Construction of single quantum deletion codes via combinatorial conditions and adjacency matrices
- Levenshtein graphs: resolvability, automorphisms \& determining sets
- Most pseudo-copy languages are not context-free
This page was built for publication:
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5528329)