Netzwerkkodierung, sichere und zuverlässige Informationsübertragung, Extremalprobleme und Informationsflüsse
Final Report Abstract
In this project we investigated Information Flows in Networks from the reliability and security point of view. Error control problems in random network coding was one of our objectives. The random network coding approach is an effective technique for linear network coding, however it is highly susceptible to errors and adversarial attacks. Thus for its pratical applications error control is an important concept. We establish bounds and constructions for error correcting codes for operator channels introduced by Kötter and Kschischang. Furthermore we study operator channels with deletions/insertions (dimension reduction/dimension enlargement). We also established bounds and constructions for such codes. We described optimal codes detecting a given number of insertions/deletions and study a multishot model for operator channel. We determined the Shannon capacity for a model of operator channel with insertions/deletions. A model of mulfiple access operator channel is studied as well. Generic erasure correcting sets (introduced,by H. Hollmann and L. Tolhuizen) are studied. The study was motivated by iterative decoding techniques for erasure correcting codes. Iterative decoding, especially applied to LDPC codes, is an important techniques since it allows to achieve the capacity of binary erasure channels. We improve known bounds for the size of generic erasure correcting sets. We found close relation between generic erasure correcting sets and known structures like intersecting codes, covering arrays etc. We introduced and studied codes correcting asymmetric/unidirectional errors of limited magnitude. Recently these codes have attracted a lot of attention, since they have been shown to be applicable for design of reliable Multilevel Flash Memories. Several physical effects that limit the reliability and performance of Multilevel Flash memories induce errors that have low magnitude and are dominantly asymmetric. This study actually gives rise to a new subject of investigation called coding for flash memories (or flash codes). We introduced two models of parallel error channels (PEC) and study the problem of efficient transmission of messages via this channels. PEC is a bundle of m lines through which messages are parallelly transmitted. When messages are transmitted through the channel, highly correlated errors occur in respective lines and the messages at a time instance may be almost equally disturbed. We consider a model when errors are produced by binary Z-channels. We studied a security problems in statistical databases. Security-control methods suggested in the literature are classified into four general approaches: conceptual, query restriction, data perturbation, and output perturbation. We studied security problems under query SUM restrictions and solve the "group security problem" in its general form. Several extremal problems related to graph partitioning are investigated and solved. The diametric problem for the products of additive cyclic group is established. The problem of multiple-packing (list coding) for a sum-type metric is studied and asymptotically solved.
Publications
-
Error control codes for parallel asymmetric channels, IEEE Transactions on Information Theory, Vol. 54, No. 2, 831 - 836, 2008
R. Ahlswede and H. Aydinian
-
Multiple packing in sum-type metric spaces. Discrete Applied Math., Vol. 156, No. 9, 1469-1477, 2008
R. Ahlswede and V. Blinovsky
-
On error control codes for random network coding, Workshop on Network Coding: Theory and Applications, NetCod 09, 15-16 June, 68-74, 2009
R. Ahlswede and H. Aydinian
-
On q-ary codes correcting unidirectional errors of a limited magnitude, in "Codes, Polynomials, and Numbers": "Gitutiun" Publishing House of the National Academy of Sciences of the Republic of Armenia, 41-61, 2009
R. Ahlswede, H. Aydinian, L.H. Khachatrian, and L.M. Tolhuizen
-
A note on full transversals and mixed orthogonal arrays, Australasian Journal of Combinatorics, Vol.48, 133-141,2010
H. Aydinian, E. Czabarka, K. Engel, P.L, Erdos, and L. A. Szekely
