Showing 1–31 of 31 results for author: Kovačević, M

DeepNcode: Encoding-Based Protection against Bit-Flip Attacks on Neural Networks

Authors: Patrik Velčický, Jakub Breier, Mladen Kovačević, Xiaolu Hou

Abstract: Fault injection attacks are a potent threat against embedded implementations of neural network models. Several attack vectors have been proposed, such as misclassification, model extraction, and trojan/backdoor planting. Most of these attacks work by flipping bits in the memory where quantized model parameters are stored. In this paper, we introduce an encoding-based protection method against bi… ▽ More Fault injection attacks are a potent threat against embedded implementations of neural network models. Several attack vectors have been proposed, such as misclassification, model extraction, and trojan/backdoor planting. Most of these attacks work by flipping bits in the memory where quantized model parameters are stored. In this paper, we introduce an encoding-based protection method against bit-flip attacks on neural networks, titled DeepNcode. We experimentally evaluate our proposal with several publicly available models and datasets, by using state-of-the-art bit-flip attacks: BFA, T-BFA, and TA-LBF. Our results show an increase in protection margin of up to $7.6\times$ for $4-$bit and $12.4\times$ for $8-$bit quantized networks. Memory overheads start at $50\%$ of the original network size, while the time overheads are negligible. Moreover, DeepNcode does not require retraining and does not change the original accuracy of the model. △ Less

Submitted 2 June, 2024; v1 submitted 22 May, 2024; originally announced May 2024.

Gilbert-Varshamov Bound for Codes in $L_1$ Metric using Multivariate Analytic Combinatorics

Authors: Keshav Goyal, Duc Tu Dao, Mladen Kovačević, Han Mao Kiah

Abstract: Analytic combinatorics in several variables refers to a suite of tools that provide sharp asymptotic estimates for certain combinatorial quantities. In this paper, we apply these tools to determine the Gilbert--Varshamov lower bound on the rate of optimal codes in $L_1$ metric. Several different code spaces are analyzed, including the simplex and the hypercube in $\mathbb{Z^n}$, all of which are i… ▽ More Analytic combinatorics in several variables refers to a suite of tools that provide sharp asymptotic estimates for certain combinatorial quantities. In this paper, we apply these tools to determine the Gilbert--Varshamov lower bound on the rate of optimal codes in $L_1$ metric. Several different code spaces are analyzed, including the simplex and the hypercube in $\mathbb{Z^n}$, all of which are inspired by concrete data storage and transmission models such as the sticky insertion channel, the permutation channel, the adjacent transposition (bit-shift) channel, the multilevel flash memory channel, etc. △ Less

Submitted 22 February, 2024; originally announced February 2024.

Comments: 33 pages, 3 figures, submitted to IEEE Transactions on Information Theory

Vector Multispaces and Multispace Codes

Authors: Mladen Kovačević

Abstract: Basic algebraic and combinatorial properties of finite vector spaces in which individual vectors are allowed to have multiplicities larger than $ 1 $ are derived. An application in coding theory is illustrated by showing that multispace codes that are introduced here may be used in random linear network coding scenarios, and that they generalize standard subspace codes (defined in the set of all s… ▽ More Basic algebraic and combinatorial properties of finite vector spaces in which individual vectors are allowed to have multiplicities larger than $ 1 $ are derived. An application in coding theory is illustrated by showing that multispace codes that are introduced here may be used in random linear network coding scenarios, and that they generalize standard subspace codes (defined in the set of all subspaces of $ \mathbb{F}_q^n $) and extend them to an infinitely larger set of parameters. In particular, in contrast to subspace codes, multispace codes of arbitrarily large cardinality and minimum distance exist for any fixed $ n $ and $ q $. △ Less

Submitted 27 May, 2024; v1 submitted 21 December, 2023; originally announced December 2023.

MSC Class: 15A03; 94B25; 05E16; 06B99

An Information-Theoretic Analog of the Twin Paradox

Authors: Mladen Kovačević, Iosif Pinelis, Marios Kountouris

Abstract: We revisit the familiar scenario involving two parties in relative motion, in which Alice stays at rest while Bob goes on a journey at speed $βc$ along an arbitrary trajectory and reunites with Alice after a certain period of time. It is a well-known consequence of special relativity that the time that passes until they meet again is different for the two parties and is shorter in Bob's frame by a… ▽ More We revisit the familiar scenario involving two parties in relative motion, in which Alice stays at rest while Bob goes on a journey at speed $βc$ along an arbitrary trajectory and reunites with Alice after a certain period of time. It is a well-known consequence of special relativity that the time that passes until they meet again is different for the two parties and is shorter in Bob's frame by a factor of $\sqrt{1-β^2}$. We investigate how this asymmetry manifests from an information-theoretic viewpoint. Assuming that Alice and Bob transmit signals of equal average power to each other during the whole journey, and that additive white Gaussian noise is present at both sides, we show that the maximum number of bits per second that Alice can transmit reliably to Bob is always higher than the one Bob can transmit to Alice. Equivalently, the energy per bit invested by Alice is lower than that invested by Bob, meaning that the traveler is less efficient from the communication perspective, as conjectured by Jarett and Cover. △ Less

Submitted 16 April, 2024; v1 submitted 21 September, 2023; originally announced September 2023.

Comments: To appear in Europhysics Letters (EPL)

MSC Class: 83A05; 94A24; 94A40

Journal ref: EPL, vol. 146, no. 4, art. no. 42002, 2024

Optimal Error-Detecting Codes for General Asymmetric Channels via Sperner Theory

Authors: Mladen Kovačević, Dejan Vukobratović

Abstract: Several communication models that are of relevance in practice are asymmetric in the way they act on the transmitted "objects". Examples include channels in which the amplitudes of the transmitted pulses can only be decreased, channels in which the symbols can only be deleted, channels in which non-zero symbols can only be shifted to the right (e.g., timing channels), subspace channels in which th… ▽ More Several communication models that are of relevance in practice are asymmetric in the way they act on the transmitted "objects". Examples include channels in which the amplitudes of the transmitted pulses can only be decreased, channels in which the symbols can only be deleted, channels in which non-zero symbols can only be shifted to the right (e.g., timing channels), subspace channels in which the dimension of the transmitted vector space can only be reduced, unordered storage channels in which the cardinality of the stored (multi)set can only be reduced, etc. We introduce a formal definition of an asymmetric channel as a channel whose action induces a partial order on the set of all possible inputs, and show that this definition captures all the above examples. Such a general approach allows one to treat all these different models in a unified way, and to obtain a characterization of optimal error-detecting codes for many interesting asymmetric channels by using Sperner theory. △ Less

Submitted 15 August, 2022; v1 submitted 15 May, 2022; originally announced May 2022.

Comments: To be presented at the IEEE Information Theory Workshop (ITW), Mumbai, India, Nov. 2022

MSC Class: 06A07; 68P30; 68R05; 94B25; 94B60

Lattice Packings of Cross-polytopes from Reed-Solomon Codes and Sidon Sets

Authors: Mladen Kovačević

Abstract: Two constructions of lattice packings of $ n $-dimensional cross-polytopes ($ \ell_1 $ balls) are described, the density of which exceeds that of any prior construction by a factor of at least $ 2^{\frac{n}{\ln n}(1 + o(1))} $ when $ n \to \infty $. The first family of lattices is explicit and is obtained by applying Construction A to a class of Reed-Solomon codes. The second family has subexponen… ▽ More Two constructions of lattice packings of $ n $-dimensional cross-polytopes ($ \ell_1 $ balls) are described, the density of which exceeds that of any prior construction by a factor of at least $ 2^{\frac{n}{\ln n}(1 + o(1))} $ when $ n \to \infty $. The first family of lattices is explicit and is obtained by applying Construction A to a class of Reed-Solomon codes. The second family has subexponential construction complexity and is based on the notion of Sidon sets in finite Abelian groups. The construction based on Sidon sets also gives the highest known asymptotic density of packing discrete cross-polytopes of fixed radius $ r \geqslant 3 $ in $ \mathbb{Z}^n $. △ Less

Submitted 26 May, 2022; v1 submitted 5 November, 2021; originally announced November 2021.

Comments: 7 pages. v2: Section 2 and the discussion after the proof of Theorem 3.1 are added, v3: minor changes. To appear in the Bulletin of the London Mathematical Society

MSC Class: 11H31; 52C17; 05B40; 11B83; 11H71; 11T71

Journal ref: Bull. London Math. Soc., vol. 54, no. 6, pp. 2372-2378, 2022

Asymptotic Behavior and Typicality Properties of Runlength-Limited Sequences

Authors: Mladen Kovačević, Dejan Vukobratović

Abstract: 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 combinatoric… ▽ More 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. △ Less

Submitted 11 December, 2021; v1 submitted 10 May, 2021; originally announced May 2021.

Comments: 13 pages (double-column), 1 figure

MSC Class: 05A15; 05A16; 68R05; 68R15; 94A55; 94A99; 94B20; 94B50; 94B65

Journal ref: IEEE Trans. Inform. Theory, vol. 68, no. 3, pp. 1638-1650, 2022

Evolutionary computational platform for the automatic discovery of nanocarriers for cancer treatment

Authors: Namid Stillman, Igor Balaz, Antisthenis Tsompanas, Marina Kovacevic, Sepinoud Azimi, Sebastien Lafond, Andrew Adamatzky, Sabine Hauert

Abstract: We present the EVONANO platform for the evolution of nanomedicines with application to anti-cancer treatments. EVONANO includes a simulator to grow tumours, extract representative scenarios, and then simulate nanoparticle transport through these scenarios to predict nanoparticle distribution. The nanoparticle designs are optimised using machine learning to efficiently find the most effective anti-… ▽ More We present the EVONANO platform for the evolution of nanomedicines with application to anti-cancer treatments. EVONANO includes a simulator to grow tumours, extract representative scenarios, and then simulate nanoparticle transport through these scenarios to predict nanoparticle distribution. The nanoparticle designs are optimised using machine learning to efficiently find the most effective anti-cancer treatments. We demonstrate our platform with two examples optimising the properties of nanoparticles and treatment to selectively kill cancer cells over a range of tumour environments. △ Less

Submitted 1 February, 2021; originally announced February 2021.

Comments: 30 pages, 4 figures

On the Maximum Entropy of a Sum of Independent Discrete Random Variables

Authors: Mladen Kovačević

Abstract: Let $ X_1, \ldots, X_n $ be independent random variables taking values in the alphabet $ \{0, 1, \ldots, r\} $, and $ S_n = \sum_{i = 1}^n X_i $. The Shepp--Olkin theorem states that, in the binary case ($ r = 1 $), the Shannon entropy of $ S_n $ is maximized when all the $ X_i $'s are uniformly distributed, i.e., Bernoulli(1/2). In an attempt to generalize this theorem to arbitrary finite alphabe… ▽ More Let $ X_1, \ldots, X_n $ be independent random variables taking values in the alphabet $ \{0, 1, \ldots, r\} $, and $ S_n = \sum_{i = 1}^n X_i $. The Shepp--Olkin theorem states that, in the binary case ($ r = 1 $), the Shannon entropy of $ S_n $ is maximized when all the $ X_i $'s are uniformly distributed, i.e., Bernoulli(1/2). In an attempt to generalize this theorem to arbitrary finite alphabets, we obtain a lower bound on the maximum entropy of $ S_n $ and prove that it is tight in several special cases. In addition to these special cases, an argument is presented supporting the conjecture that the bound represents the optimal value for all $ n, r $, i.e., that $ H(S_n) $ is maximized when $ X_1, \ldots, X_{n-1} $ are uniformly distributed over $ \{0, r\} $, while the probability mass function of $ X_n $ is a mixture (with explicitly defined non-zero weights) of the uniform distributions over $ \{0, r\} $ and $ \{1, \ldots, r-1\} $. △ Less

Submitted 7 May, 2022; v1 submitted 3 August, 2020; originally announced August 2020.

Comments: 8 pages, 1 figure

MSC Class: 94A17 (Primary) 60C05; 60G50 (Secondary)

Journal ref: Theory Probab. Appl., vol. 66, no. 3, pp. 482-487, 2021

Signaling to Relativistic Observers: An Einstein-Shannon-Riemann Encounter

Authors: Mladen Kovačević

Abstract: A communication scenario is described involving a series of events triggered by a transmitter and observed by a receiver experiencing relativistic time dilation. The message selected by the transmitter is assumed to be encoded in the events' timings and is required to be perfectly recovered by the receiver, regardless of the difference in clock rates in the two frames of reference. It is shown tha… ▽ More A communication scenario is described involving a series of events triggered by a transmitter and observed by a receiver experiencing relativistic time dilation. The message selected by the transmitter is assumed to be encoded in the events' timings and is required to be perfectly recovered by the receiver, regardless of the difference in clock rates in the two frames of reference. It is shown that the largest proportion of the space of all $ k $-event signals that can be selected as a code ensuring error-free information transfer in this setting equals $ ζ(k)^{-1} $, where $ ζ$ is the Riemann zeta function. △ Less

Submitted 27 August, 2021; v1 submitted 7 May, 2020; originally announced May 2020.

Comments: 4 pages (double-column), 1 figure

MSC Class: 83A05; 94A24; 94A40; 94B25; 94B50; 11A41; 11Z05

Journal ref: Probl. Inf. Transm., vol. 56, no. 4, pp. 303-308, Dec. 2020

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

Authors: Mladen Kovačević

Abstract: The set of all $ q $-ary strings that do not contain repeated substrings of length $ \leqslant\! 3 $ (i.e., that do not contain substrings of the form $ a a $, $ a b a b $, and $ a b c a b c $) constitutes a code correcting an arbitrary number of tandem-duplication mutations of length $ \leqslant\! 3 $. In other words, any two such strings are non-confusable in the sense that they cannot produce t… ▽ More The set of all $ q $-ary strings that do not contain repeated substrings of length $ \leqslant\! 3 $ (i.e., that do not contain substrings of the form $ a a $, $ a b a b $, and $ a b c a b c $) constitutes a code correcting an arbitrary number of tandem-duplication mutations of length $ \leqslant\! 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 $ \leqslant\! 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. △ Less

Submitted 24 April, 2022; v1 submitted 15 November, 2019; originally announced November 2019.

Comments: 10 pages

MSC Class: 94A24; 94A40; 94B25; 94B50; 68R15

Journal ref: Probl. Inf. Transm., vol. 58, no. 2, pp. 111-121, 2022

Second- and Third-Order Asymptotics of the Continuous-Time Poisson Channel

Authors: Yuta Sakai, Vincent Y. F. Tan, Mladen Kovačević

Abstract: The paper derives the optimal second-order coding rate for the continuous-time Poisson channel. We also obtain bounds on the third-order coding rate. This is the first instance of a second-order result for a continuous-time channel. The converse proof hinges on a novel construction of an output distribution induced by Wyner's discretized channel and the construction of an appropriate $ε$-net of th… ▽ More The paper derives the optimal second-order coding rate for the continuous-time Poisson channel. We also obtain bounds on the third-order coding rate. This is the first instance of a second-order result for a continuous-time channel. The converse proof hinges on a novel construction of an output distribution induced by Wyner's discretized channel and the construction of an appropriate $ε$-net of the input probability simplex. While the achievability proof follows the general program to prove the third-order term for non-singular discrete memoryless channels put forth by Polyanskiy, several non-standard techniques -- such as new definitions and bounds on the probabilities of typical sets using logarithmic Sobolev inequalities -- are employed to handle the continuous nature of the channel. △ Less

Submitted 1 April, 2020; v1 submitted 25 March, 2019; originally announced March 2019.

Comments: 26 pages, to appear in the IEEE Transactions on Information Theory, vol. 66, 2020

Journal ref: IEEE Trans. Inform. Theory, vol. 66, no. 8, pp. 4742-4760, Aug. 2020

Zero-Error Capacity of Duplication Channels

Authors: Mladen Kovačević

Abstract: This paper is concerned with the problem of error-free communication over the i.i.d. duplication channel which acts on a transmitted sequence $ x_1 \cdots x_n $ by inserting a random number of copies of each symbol $ x_i $ next to the original symbol. The random variables representing the numbers of inserted copies at each position $ i $ are independent and take values in $ \{0, 1, \ldots, r\} $,… ▽ More This paper is concerned with the problem of error-free communication over the i.i.d. duplication channel which acts on a transmitted sequence $ x_1 \cdots x_n $ by inserting a random number of copies of each symbol $ x_i $ next to the original symbol. The random variables representing the numbers of inserted copies at each position $ i $ are independent and take values in $ \{0, 1, \ldots, r\} $, where $ r $ is a fixed parameter. A more general model in which blocks of $ \ell $ consecutive symbols are being duplicated, and which is inspired by DNA-based data storage systems wherein the stored molecules are subject to tandem-duplication mutations, is also analyzed. A construction of optimal codes correcting all patterns of errors of this type is described, and the zero-error capacity of the duplication channel---the largest rate at which information can be transmitted through it in an error-free manner---is determined for each $ \ell $ and $ r $. △ Less

Submitted 23 July, 2019; v1 submitted 17 February, 2019; originally announced February 2019.

Comments: 8 pages (double-column), 4 figures. Accepted for publication in IEEE Transactions on Communications

MSC Class: 94A24; 94B25; 94B50; 68P30; 68R05

Journal ref: IEEE Trans. Commun., vol. 67, no. 10, pp. 6735-6742, Oct. 2019

Some Enumeration Problems in the Duplication-Loss Model of Genome Rearrangement

Authors: Mladen Kovačević, Sanja Brdar, Vladimir Crnojević

Abstract: Tandem-duplication-random-loss (TDRL) is an important genome rearrangement operation studied in evolutionary biology. This paper investigates some of the formal properties of TDRL operations on the symmetric group (the space of permutations over an $ n $-set). In particular, the cardinality of `balls' of radius one in the TDRL metric, as well as the cardinality of the maximum intersection of two s… ▽ More Tandem-duplication-random-loss (TDRL) is an important genome rearrangement operation studied in evolutionary biology. This paper investigates some of the formal properties of TDRL operations on the symmetric group (the space of permutations over an $ n $-set). In particular, the cardinality of `balls' of radius one in the TDRL metric, as well as the cardinality of the maximum intersection of two such balls, are determined. The corresponding problems for the so-called mirror (or palindromic) TDRL rearrangement operations are also solved. The results represent an initial step in the study of error correction and reconstruction problems in this context and are of potential interest in DNA-based data storage applications. △ Less

Submitted 6 June, 2019; v1 submitted 1 February, 2019; originally announced February 2019.

Comments: 5 pages (double-column). To be presented at the 2019 IEEE International Symposium on Information Theory (ISIT), Paris, France

MSC Class: 05A05; 68R05; 92B99; 92D20; 94B25

Asymptotically Optimal Codes Correcting Fixed-Length Duplication Errors in DNA Storage Systems

Authors: Mladen Kovačević, Vincent Y. F. Tan

Abstract: A (tandem) duplication of length $ k $ is an insertion of an exact copy of a substring of length $ k $ next to its original position. This and related types of impairments are of relevance in modeling communication in the presence of synchronization errors, as well as in several information storage applications. We demonstrate that Levenshtein's construction of binary codes correcting insertions o… ▽ More A (tandem) duplication of length $ k $ is an insertion of an exact copy of a substring of length $ k $ next to its original position. This and related types of impairments are of relevance in modeling communication in the presence of synchronization errors, as well as in several information storage applications. We demonstrate that Levenshtein's construction of binary codes correcting insertions of zeros is, with minor modifications, applicable also to channels with arbitrary alphabets and with duplication errors of arbitrary (but fixed) length $ k $. Furthermore, we derive bounds on the cardinality of optimal $ q $-ary codes correcting up to $ t $ duplications of length $ k $, and establish the following corollaries in the asymptotic regime of growing block-length: 1.) the presented family of codes is optimal for every $ q, t, k $, in the sense of the asymptotic scaling of code redundancy; 2.) the upper bound, when specialized to $ q = 2 $, $ k = 1 $, improves upon Levenshtein's bound for every $ t \geq 3 $; 3.) the bounds coincide for $ t = 1 $, thus yielding the exact asymptotic behavior of the size of optimal single-duplication-correcting codes. △ Less

Submitted 30 August, 2018; originally announced August 2018.

Comments: To appear in IEEE Communications Letters

MSC Class: 94B20; 94B25; 94B50; 94B65; 68P20; 68P30; 68R05

Journal ref: IEEE Commun. Lett., vol. 22, no. 11, pp. 2194-2197, Nov. 2018

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

Authors: Mladen Kovačević

Abstract: 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 \leq d < k \leq \infty $). 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… ▽ More 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 \leq d < k \leq \infty $). 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. △ Less

Submitted 14 March, 2019; v1 submitted 16 March, 2018; originally announced March 2018.

Comments: 10 pages (double-column), 2 figures. To appear in IEEE Transactions on Information Theory

MSC Class: 94B25; 94B50; 94B65; 94A55

Journal ref: IEEE Trans. Inform. Theory, vol. 65, no. 8, pp. 4804-4814, Aug. 2019

Fundamental Limits of Communication Over State-Dependent Channels With Feedback

Authors: Mladen Kovačević, Carol Wang, Vincent Y. F. Tan

Abstract: The fundamental limits of communication over state-dependent discrete memoryless channels with noiseless feedback are studied, under the assumption that the communicating parties are allowed to use variable-length coding schemes. Various cases are analyzed, with the employed coding schemes having either bounded or unbounded codeword lengths, and with state information revealed to the encoder and/o… ▽ More The fundamental limits of communication over state-dependent discrete memoryless channels with noiseless feedback are studied, under the assumption that the communicating parties are allowed to use variable-length coding schemes. Various cases are analyzed, with the employed coding schemes having either bounded or unbounded codeword lengths, and with state information revealed to the encoder and/or decoder in a strictly causal, causal, or non-causal manner. In each of these settings, necessary and sufficient conditions for positivity of the zero-error capacity are obtained and it is shown that, whenever the zero-error capacity is positive, it equals the conventional vanishing-error capacity. Moreover, it is shown that the vanishing-error capacity of state-dependent channels is not increased by the use of feedback and variable-length coding. Both these kinds of capacities of state-dependent channels with feedback are thus fully characterized. △ Less

Submitted 15 January, 2019; v1 submitted 20 December, 2017; originally announced December 2017.

Comments: 10 pages. To appear in IEEE Transactions on Communications

MSC Class: 94A24; 94A45; 68P30

Journal ref: IEEE Trans. Commun., vol. 67, no. 5, pp. 3182-3191, May 2019

A Note on Parallel Asynchronous Channels with Arbitrary Skews

Authors: Mladen Kovačević

Abstract: A zero-error coding scheme of asymptotic rate $ \log_2 (1+\sqrt{5}) - 1 $ was recently described for a communication channel composed of parallel asynchronous lines satisfying the so-called no switch assumption. We prove that this is in fact the highest rate attainable, i.e., the zero-error capacity of this channel. A zero-error coding scheme of asymptotic rate $ \log_2 (1+\sqrt{5}) - 1 $ was recently described for a communication channel composed of parallel asynchronous lines satisfying the so-called no switch assumption. We prove that this is in fact the highest rate attainable, i.e., the zero-error capacity of this channel. △ Less

Submitted 26 October, 2017; originally announced October 2017.

MSC Class: 94A24; 94B50

Journal ref: IEEE Trans. Inform. Theory, vol. 63, no. 11, pp. 7320-7321, Nov. 2017

On Error Detection in Asymmetric Channels

Authors: Mladen Kovačević

Abstract: We study the error detection problem in $ q $-ary asymmetric channels wherein every input symbol $ x_i $ is mapped to an output symbol $ y_i $ satisfying $ y_i \geq x_i $. A general setting is assumed where the noise vectors are (potentially) restricted in: 1) the amplitude, $ y_i - x_i \leq a $, 2) the Hamming weight, $ \sum_{i=1}^n 1_{\{y_i \neq x_i\}} \leq h $, and 3) the total weight,… ▽ More We study the error detection problem in $ q $-ary asymmetric channels wherein every input symbol $ x_i $ is mapped to an output symbol $ y_i $ satisfying $ y_i \geq x_i $. A general setting is assumed where the noise vectors are (potentially) restricted in: 1) the amplitude, $ y_i - x_i \leq a $, 2) the Hamming weight, $ \sum_{i=1}^n 1_{\{y_i \neq x_i\}} \leq h $, and 3) the total weight, $ \sum_{i=1}^n (y_i - x_i) \leq t $. Optimal codes detecting these types of errors are described for certain sets of parameters $ a, h, t $, both in the standard and in the cyclic ($ \operatorname{mod}\, q $) version of the problem. It is also demonstrated that these codes are optimal in the large alphabet limit for every $ a, h, t $ and every block-length $ n $. △ Less

Submitted 9 September, 2017; v1 submitted 14 June, 2017; originally announced June 2017.

Comments: 4 pages, 2 figures

MSC Class: 94B05; 94B25; 05D99; 68P30; 68R05

Journal ref: IEEE Commun. Lett., vol. 21, no. 9, pp. 1933-1936, Sep. 2017

Codes in the Space of Multisets---Coding for Permutation Channels with Impairments

Authors: Mladen Kovačević, Vincent Y. F. Tan

Abstract: Motivated by communication channels in which the transmitted sequences are subject to random permutations, as well as by certain DNA storage systems, we study the error control problem in settings where the information is stored/transmitted in the form of multisets of symbols from a given finite alphabet. A general channel model is assumed in which the transmitted multisets are potentially impaire… ▽ More Motivated by communication channels in which the transmitted sequences are subject to random permutations, as well as by certain DNA storage systems, we study the error control problem in settings where the information is stored/transmitted in the form of multisets of symbols from a given finite alphabet. A general channel model is assumed in which the transmitted multisets are potentially impaired by insertions, deletions, substitutions, and erasures of symbols. Several constructions of error-correcting codes for this channel are described, and bounds on the size of optimal codes correcting any given number of errors derived. The construction based on the notion of Sidon sets in finite Abelian groups is shown to be optimal, in the sense of the asymptotic scaling of code redundancy, for any "error radius" and any alphabet size. It is also shown to be optimal in the stronger sense of maximal code cardinality in various cases. △ Less

Submitted 21 June, 2018; v1 submitted 28 December, 2016; originally announced December 2016.

Comments: 14 pages, 5 figures. v1: conference version (ISIT'17). v5: extended version (IEEE Trans. Inf. Theory), includes parts of arXiv:1409.5276

MSC Class: 94B25; 94B65; 94A40; 68P30; 68R05

Journal ref: IEEE Trans. Inform. Theory, vol. 64, no. 7, pp. 5156-5169, Jul. 2018

Improved Bounds on Sidon Sets via Lattice Packings of Simplices

Authors: Mladen Kovačević, Vincent Y. F. Tan

Abstract: A $ B_h $ set (or Sidon set of order $ h $) in an Abelian group $ G $ is any subset $ \{b_0, b_1, \ldots,b_{n}\} $ of $ G $ with the property that all the sums $ b_{i_1} + \cdots + b_{i_h} $ are different up to the order of the summands. Let $ φ(h,n) $ denote the order of the smallest Abelian group containing a $ B_h $ set of cardinality $ n + 1 $. It is shown that \[ \lim_{h \to \infty} \frac{ φ(… ▽ More A $ B_h $ set (or Sidon set of order $ h $) in an Abelian group $ G $ is any subset $ \{b_0, b_1, \ldots,b_{n}\} $ of $ G $ with the property that all the sums $ b_{i_1} + \cdots + b_{i_h} $ are different up to the order of the summands. Let $ φ(h,n) $ denote the order of the smallest Abelian group containing a $ B_h $ set of cardinality $ n + 1 $. It is shown that \[ \lim_{h \to \infty} \frac{ φ(h,n) }{ h^n } = \frac{1}{n! δ_L(\triangle^n)} , \] where $ δ_L(\triangle^n) $ is the lattice packing density of an $ n $-simplex in Euclidean space. This determines the asymptotics exactly in cases where this density is known ($ n \leq 3 $) and gives improved bounds on $ φ(h,n) $ in the remaining cases. The corresponding geometric characterization of bases of order $ h $ in finite Abelian groups in terms of lattice coverings by simplices is also given. △ Less

Submitted 28 September, 2017; v1 submitted 5 October, 2016; originally announced October 2016.

Comments: 9 pages, 2 figures

MSC Class: 05B10; 05B40; 11B13; 11B75; 11B83; 11H31; 52C17; 94B65; 20K99

Journal ref: SIAM J. Discrete Math., vol. 31, no. 3, pp. 2269-2278, 2017

Zero-Error Capacity of $P$-ary Shift Channels and FIFO Queues

Authors: Mladen Kovačević, Miloš Stojaković, Vincent Y. F. Tan

Abstract: The objects of study of this paper are communication channels in which the dominant type of noise are symbol shifts, the main motivating examples being timing and bit-shift channels. Two channel models are introduced and their zero-error capacities and zero-error-detection capacities determined by explicit constructions of optimal codes. Model A can be informally described as follows: 1) The infor… ▽ More The objects of study of this paper are communication channels in which the dominant type of noise are symbol shifts, the main motivating examples being timing and bit-shift channels. Two channel models are introduced and their zero-error capacities and zero-error-detection capacities determined by explicit constructions of optimal codes. Model A can be informally described as follows: 1) The information is stored in an $ n $-cell register, where each cell is either empty or contains a particle of one of $ P $ possible types, and 2) due to the imperfections of the device each of the particles may be shifted several cells away from its original position over time. Model B is an abstraction of a single-server queue: 1) The transmitter sends packets from a $ P $-ary alphabet through a queuing system with an infinite buffer and a First-In-First-Out (FIFO) service procedure, and 2) each packet is being processed by the server for a random number of time slots. More general models including additional types of noise that the particles/packets can experience are also studied, as are the continuous-time versions of these problems. △ Less

Submitted 10 September, 2017; v1 submitted 9 May, 2016; originally announced May 2016.

Comments: 10 pages (double-column), 3 figures. v2: title changed, material reorganized. Accepted for publication in IEEE Transactions on Information Theory (the Appendix will not appear in the published article)

MSC Class: 94A24; 94A40; 94B25; 94B50

Journal ref: IEEE Trans. Inform. Theory, vol. 63, no. 12, pp. 7698-7707, Dec. 2017

Sidon Sets, Difference Sets, and Codes in $ A_n $ Lattices

Authors: Mladen Kovačević

Abstract: This chapter investigates the properties of (linear) codes in $ A_n $ lattices, the practical motivation for which is found in several communication scenarios, such as asymmetric channels, sticky-insertion channels, bit-shift channels, and permutation channels. In particular, a connection between these codes and notions of difference sets and Sidon sets in Abelian groups is demonstrated. It is sho… ▽ More This chapter investigates the properties of (linear) codes in $ A_n $ lattices, the practical motivation for which is found in several communication scenarios, such as asymmetric channels, sticky-insertion channels, bit-shift channels, and permutation channels. In particular, a connection between these codes and notions of difference sets and Sidon sets in Abelian groups is demonstrated. It is shown that the $ A_n $ lattice admits a linear perfect code of radius $ 1 $ if and only if there exists an Abelian planar difference set of cardinality $ n + 1 $. Similarly, a direct link is given between linear codes of radius $ r $ in the $ A_n $ lattice and Sidon sets of order $ 2r $ and cardinality $ n + 1 $. Sidon sets of order $ 2r-1 $ are also represented geometrically in a similar way. Apart from providing geometric intuition about Sidon sets, this interpretation enables simple derivations of bounds on their parameters, which are either equivalent to, or improve upon the known bounds. In connection to the above, more general (non-planar) Abelian difference sets and perfect codes of radius $ r $ are also discussed. △ Less

Submitted 15 November, 2019; v1 submitted 18 September, 2014; originally announced September 2014.

Comments: 15 pages (single-column format), 8 figures

MSC Class: 05B10; 05B40; 05B45; 11B75; 11T71; 52C17; 52C22; 94B25

Information-Geometric Equivalence of Transportation Polytopes

Authors: Mladen Kovačević, Ivan Stanojević, Vojin Šenk

Abstract: This paper deals with transportation polytopes in the probability simplex (that is, sets of categorical bivariate probability distributions with prescribed marginals). Information projections between such polytopes are studied, and a sufficient condition is described under which these mappings are homeomorphisms. This paper deals with transportation polytopes in the probability simplex (that is, sets of categorical bivariate probability distributions with prescribed marginals). Information projections between such polytopes are studied, and a sufficient condition is described under which these mappings are homeomorphisms. △ Less

Submitted 6 July, 2015; v1 submitted 13 February, 2014; originally announced February 2014.

Comments: 6 pages, 1 figure. v2: A remark concerning Frechet-Hoeffding bounds is added

MSC Class: 94A17; 52B11; 52B12; 62B10; 62H17; 54C99

Journal ref: Probl. Inf. Transm., vol. 51, no. 2, pp. 103-109, Apr. 2015

Zero-Error Capacity of a Class of Timing Channels

Authors: Mladen Kovačević, Petar Popovski

Abstract: We analyze the problem of zero-error communication through timing channels that can be interpreted as discrete-time queues with bounded waiting times. The channel model includes the following assumptions: 1) Time is slotted, 2) at most $ N $ "particles" are sent in each time slot, 3) every particle is delayed in the channel for a number of slots chosen randomly from the set… ▽ More We analyze the problem of zero-error communication through timing channels that can be interpreted as discrete-time queues with bounded waiting times. The channel model includes the following assumptions: 1) Time is slotted, 2) at most $ N $ "particles" are sent in each time slot, 3) every particle is delayed in the channel for a number of slots chosen randomly from the set $ \{0, 1, \ldots, K\} $, and 4) the particles are identical. It is shown that the zero-error capacity of this channel is $ \log r $, where $ r $ is the unique positive real root of the polynomial $ x^{K+1} - x^{K} - N $. Capacity-achieving codes are explicitly constructed, and a linear-time decoding algorithm for these codes devised. In the particular case $ N = 1 $, $ K = 1 $, the capacity is equal to $ \log φ$, where $ φ= (1 + \sqrt{5}) / 2 $ is the golden ratio, and the constructed codes give another interpretation of the Fibonacci sequence. △ Less

Submitted 24 August, 2014; v1 submitted 6 November, 2013; originally announced November 2013.

Comments: 5 pages (double-column), 3 figures. v3: Section IV.1 from v2 is replaced with Remark 1, and Section IV.2 is removed. Accepted for publication in IEEE Transactions on Information Theory

MSC Class: 94B25; 94A40; 94A24; 68R05; 65Q30

Journal ref: IEEE Trans. Inform. Theory, vol. 60, no. 11, pp. 6796-6800, Nov. 2014

Perfect Codes in the Discrete Simplex

Authors: Mladen Kovačević, Dejan Vukobratović

Abstract: We study the problem of existence of (nontrivial) perfect codes in the discrete $ n $-simplex $ Δ_{\ell}^n := \left\{ \begin{pmatrix} x_0, \ldots, x_n \end{pmatrix} : x_i \in \mathbb{Z}_{+}, \sum_i x_i = \ell \right\} $ under $ \ell_1 $ metric. The problem is motivated by the so-called multiset codes, which have recently been introduced by the authors as appropriate constructs for error correction… ▽ More We study the problem of existence of (nontrivial) perfect codes in the discrete $ n $-simplex $ Δ_{\ell}^n := \left\{ \begin{pmatrix} x_0, \ldots, x_n \end{pmatrix} : x_i \in \mathbb{Z}_{+}, \sum_i x_i = \ell \right\} $ under $ \ell_1 $ metric. The problem is motivated by the so-called multiset codes, which have recently been introduced by the authors as appropriate constructs for error correction in the permutation channels. It is shown that $ e $-perfect codes in the $ 1 $-simplex $ Δ_{\ell}^1 $ exist for any $ \ell \geq 2e + 1 $, the $ 2 $-simplex $ Δ_{\ell}^2 $ admits an $ e $-perfect code if and only if $ \ell = 3e + 1 $, while there are no perfect codes in higher-dimensional simplices. In other words, perfect multiset codes exist only over binary and ternary alphabets. △ Less

Submitted 5 November, 2013; v1 submitted 11 July, 2013; originally announced July 2013.

Comments: 15 pages (single-column), 5 figures. Minor revisions made. Accepted for publication in Designs, Codes and Cryptography

MSC Class: 94B25; 05B40; 52C17; 05C12; 68R99

Journal ref: Des. Codes Cryptogr., vol. 75, no. 1, pp. 81-95, Apr. 2015

On the Entropy of Couplings

Authors: Mladen Kovačević, Ivan Stanojević, Vojin Šenk

Abstract: In this paper, some general properties of Shannon information measures are investigated over sets of probability distributions with restricted marginals. Certain optimization problems associated with these functionals are shown to be NP-hard, and their special cases are found to be essentially information-theoretic restatements of well-known computational problems, such as the SUBSET SUM and the… ▽ More In this paper, some general properties of Shannon information measures are investigated over sets of probability distributions with restricted marginals. Certain optimization problems associated with these functionals are shown to be NP-hard, and their special cases are found to be essentially information-theoretic restatements of well-known computational problems, such as the SUBSET SUM and the 3-PARTITION. The notion of minimum entropy coupling is introduced and its relevance is demonstrated in information-theoretic, computational, and statistical contexts. Finally, a family of pseudometrics (on the space of discrete probability distributions) defined by these couplings is studied, in particular their relation to the total variation distance, and a new characterization of the conditional entropy is given. △ Less

Submitted 22 March, 2015; v1 submitted 13 March, 2013; originally announced March 2013.

Comments: 18 pages (single-column). Compared to v1, the material is reorganized, Section IV.C is removed (the results will possible appear elsewhere), Propositions 3.2 and 3.7 are added. Accepted for publication in Information and Computation

MSC Class: 94A17; 60E99; 68Q17

Journal ref: Inf. Comput., vol. 242, pp. 369-382, June 2015

Multiset Codes for Permutation Channels

Authors: Mladen Kovačević, Dejan Vukobratović

Abstract: This paper introduces the notion of multiset codes as relevant to the problem of reliable information transmission over permutation channels. The motivation for studying permutation channels comes from the effect of out of order delivery of packets in some types of packet networks. The proposed codes are a generalization of the so-called subset codes, recently proposed by the authors. Some of the… ▽ More This paper introduces the notion of multiset codes as relevant to the problem of reliable information transmission over permutation channels. The motivation for studying permutation channels comes from the effect of out of order delivery of packets in some types of packet networks. The proposed codes are a generalization of the so-called subset codes, recently proposed by the authors. Some of the basic properties of multiset codes are established, among which their equivalence to integer codes under the Manhattan metric. The presented coding-theoretic framework follows closely the one proposed by Koetter and Kschischang for the operator channels. The two mathematical models are similar in many respects, and the basic idea is presented in a way which admits a unified view on coding for these types of channels. △ Less

Submitted 31 January, 2013; originally announced January 2013.

Comments: 5 pages

MSC Class: 94B60

Subset Codes for Packet Networks

Authors: Mladen Kovačević, Dejan Vukobratović

Abstract: In this paper, we present a coding-theoretic framework for message transmission over packet-switched networks. Network is modeled as a channel which can induce packet errors, deletions, insertions, and out of order delivery of packets. The proposed approach can be viewed as an extension of the one introduced by Koetter and Kschischang for networks based on random linear network coding. Namely, whi… ▽ More In this paper, we present a coding-theoretic framework for message transmission over packet-switched networks. Network is modeled as a channel which can induce packet errors, deletions, insertions, and out of order delivery of packets. The proposed approach can be viewed as an extension of the one introduced by Koetter and Kschischang for networks based on random linear network coding. Namely, while their framework is based on subspace codes and designed for networks in which network nodes perform random linear combining of the packets, ours is based on the so-called subset codes, and is designed for networks employing routing in network nodes. △ Less

Submitted 27 February, 2013; v1 submitted 27 October, 2012; originally announced October 2012.

Comments: 4 pages

MSC Class: 94B60

Journal ref: IEEE Commun. Lett., vol. 17, no. 4, pp. 729-732, Apr. 2013

On the Hardness of Entropy Minimization and Related Problems

Authors: Mladen Kovačević, Ivan Stanojević, Vojin Šenk

Abstract: We investigate certain optimization problems for Shannon information measures, namely, minimization of joint and conditional entropies $H(X,Y)$, $H(X|Y)$, $H(Y|X)$, and maximization of mutual information $I(X;Y)$, over convex regions. When restricted to the so-called transportation polytopes (sets of distributions with fixed marginals), very simple proofs of NP-hardness are obtained for these prob… ▽ More We investigate certain optimization problems for Shannon information measures, namely, minimization of joint and conditional entropies $H(X,Y)$, $H(X|Y)$, $H(Y|X)$, and maximization of mutual information $I(X;Y)$, over convex regions. When restricted to the so-called transportation polytopes (sets of distributions with fixed marginals), very simple proofs of NP-hardness are obtained for these problems because in that case they are all equivalent, and their connection to the well-known \textsc{Subset sum} and \textsc{Partition} problems is revealed. The computational intractability of the more general problems over arbitrary polytopes is then a simple consequence. Further, a simple class of polytopes is shown over which the above problems are not equivalent and their complexity differs sharply, namely, minimization of $H(X,Y)$ and $H(Y|X)$ is trivial, while minimization of $H(X|Y)$ and maximization of $I(X;Y)$ are strongly NP-hard problems. Finally, two new (pseudo)metrics on the space of discrete probability distributions are introduced, based on the so-called variation of information quantity, and NP-hardness of their computation is shown. △ Less

Submitted 5 July, 2012; originally announced July 2012.

Comments: IEEE Information Theory Workshop (ITW) 2012

MSC Class: 94A17; 68Q17

Some Properties of Rényi Entropy over Countably Infinite Alphabets

Authors: Mladen Kovačević, Ivan Stanojević, Vojin Šenk

Abstract: In this paper we study certain properties of Rényi entropy functionals $H_α(\mathcal{P})$ on the space of probability distributions over $\mathbb{Z}_+$. Primarily, continuity and convergence issues are addressed. Some properties shown parallel those known in the finite alphabet case, while others illustrate a quite different behaviour of Rényi entropy in the infinite case. In particular, it is sho… ▽ More In this paper we study certain properties of Rényi entropy functionals $H_α(\mathcal{P})$ on the space of probability distributions over $\mathbb{Z}_+$. Primarily, continuity and convergence issues are addressed. Some properties shown parallel those known in the finite alphabet case, while others illustrate a quite different behaviour of Rényi entropy in the infinite case. In particular, it is shown that, for any distribution $\mathcal P$ and any $r\in[0,\infty]$, there exists a sequence of distributions $\mathcal{P}_n$ converging to $\mathcal{P}$ with respect to the total variation distance, such that $\lim_{n\to\infty}\lim_{α\to{1+}} H_α(\mathcal{P}_n) = \lim_{α\to{1+}}\lim_{n\to\infty} H_α(\mathcal{P}_n) + r$. △ Less

Submitted 27 February, 2013; v1 submitted 25 June, 2011; originally announced June 2011.

Comments: 13 pages (single-column)

MSC Class: 94A17 ACM Class: H.1.1

Journal ref: Probl. Inf. Transm., vol. 49, no. 2, pp. 99-110, Apr. 2013