Interactive Communication, Diagnosis and Error Control in Networks

DOI10.1007/978-3-642-02094-0_10MaRDI QIDQ3637318zbMATH OpenOpenAlexFDO

Authors Harout Aydinian, Rudolf Ahlswede

Publication date 9 July 2009

Published in Algorithmics of Large and Complex Networks (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1108.1161

Mathematics Subject Classification ID

Network design and communication in computer systems (68M10) Reliability, testing and fault tolerance of networks and computer systems (68M15) Communication networks in operations research (90B18) Communication theory (94A05)

Abstract: Motivated by iterative decoding techniques for the binary erasure channel Hollmann and Tolhuizen introduced and studied the notion of generic erasure correcting sets for linear codes. A generic $(r,s)$--erasure correcting set generates for all codes of codimension $r$ a parity check matrix that allows iterative decoding of all correctable erasure patterns of size $s$ or less. The problem is to derive bounds on the minimum size $F(r,s)$ of generic erasure correcting sets and to find constructions for such sets. In this paper we continue the study of these sets. We derive better lower and upper bounds. Hollmann and Tolhuizen also introduced the stronger notion of $(r,s)$--sets and derived bounds for their minimum size $G(r,s)$. Here also we improve these bounds. We observe that these two conceps are closely related to so called $s$--wise intersecting codes, an area, in which $G(r,s)$ has been studied primarily with respect to ratewise performance. We derive connections. Finally, we observed that hypergraph covering can be used for both problems to derive good upper bounds.

Recommendations

• On diagnosability of large multiprocessor networks
• On the diagnosing algorithm for networks
• On diagnosability of large multiprocessor networks
• Vertex identifying codes for fault isolation in communication networks
• System diagnosis with smallest risk of error

Cites work

• An extremal problem on graphs
• An Interpretation of Identification Entropy
• Codes for Asymmetric Limited-Magnitude Errors With Application to Multilevel Flash Memories
• Construction of asymmetric connectors of depth two
• Constructions of sparse asymmetric connectors with number theoretic methods
• Diagnosability of regular systems
• Error Control Codes for Parallel Asymmetric Channels
• Expander graphs and their applications
• Expanders that beat the eigenvalue bound: Explicit construction and applications
• scientific article; zbMATH DE number 3652373 (Why is no real title available?)
• scientific article; zbMATH DE number 3577144 (Why is no real title available?)
• scientific article; zbMATH DE number 1016362 (Why is no real title available?)
• scientific article; zbMATH DE number 1026591 (Why is no real title available?)
• scientific article; zbMATH DE number 877117 (Why is no real title available?)
• Linear network coding
• Network information flow
• Note on an extremal problem arising for unreliable networks in parallel computing
• On diagnosability of large multiprocessor networks
• On rearrangeable and non-blocking switching networks
• On sequential diagnosis of multiprocessor systems
• Optimal numberings and isoperimetric problems on graphs
• Optimal Rearrangeable Multistage Connecting Networks
• Optimization of Reduced Dependencies for Synchronous Sequential Machines
• Parallel error correcting codes
• Polynomial Time Algorithms for Multicast Network Code Construction
• Problems in Network Coding and Error Correcting Codes Appended by a Draft Version of S. Riis “Utilising Public Information in Network Coding”
• Rearrangeable Networks with Limited Depth
• Searching with lies under error cost constraints
• Sparse Asymmetric Connectors in Communication Networks
• The Noisy Channel Coding Theorem for Erasure Channels
• Wide-Sense Nonblocking Networks

Cited in

(1)

• Construction of optimal constant-dimension subspace codes

This page was built for publication: Interactive Communication, Diagnosis and Error Control in Networks

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3637318)