Validation of the transmitter's behaviour in the partial erasure channel in the case of~absence of~absolutely distinguishable characters

I. B. Kazakov

Prikladnaâ diskretnaâ matematika, no. 1 (2025), pp. 80-97.

Résumé

This paper belongs to a series of papers devoted to the partial erasure channel, in which the concepts of partial erasure structure, partial erasure channel, correct function, and correct protocol have been introduced. The partial erasure structure is a triple consisting of the alphabet $A$, a family of partitions of this alphabet, and a set of probabilities attributed to the partitions. The characters $a_1, a_2 \in A$ are called absolutely distinguishable if there is no partition such that they belong to the same class of this partition. The partial erasure channel functions as follows. Alice sends Bob a symbol $a \in A$, but Bob receives only partial information about the symbol. Bob only knows which partition has been choosen and which partition class the symbol belongs to. The behavior of the transmitter in the partial erase channel can be described by specifying a function $F: S^{*} \to A^{*}$, where $S$ is the alphabet of the input tape from which the transmitter reads information. The function $F$ uniquely defines the deterministic function $\hat{F}:S^{*} \to A^{*}$ as follows: for any word $\hat{s}\in S^{*}$, $\hat{s} = s_1 \ldots s_m$, let $\hat{F}(\hat{s}) = F(\Lambda) F(s_1) F(s_1 s_2) \ldots F(s_1 \ldots s_m)$, where $\Lambda$ is the empty word. The function $\hat{F}$ can be represented as an automaton with the input alphabet $S$ and the output alphabet $A^{*}$. The automaton, in turn, is represented as a graph whose vertices correspond to states and edges have two signatures: the symbol $s\in S$ and the word $\alpha\in A^{*}$. For the existence of a correct protocol that includes the function $F$ of the transmitter behavior, it is necessary and sufficient that the function $F$ belongs to the class of correct functions. A function is correct if and only if there is no anomaly of the second kind, which is not an anomaly of the first kind. The anomaly of the second kind is a pair of words $(\hat{s}_1, \hat{s}_2)$ such that $|\hat{s}_2| =|\hat{s}_1| + 1$, $|\hat{F}(\hat{s}_2)| \le |\hat{F}(\hat{s}_1)|$. The anomaly of the first kind is a pair of words $(\hat{s}_1, \hat{s}_2)$ such that there is an index $i$ such that the characters $\hat{F}(\hat{s}_1)[i]$ and $\hat{F}(\hat{s}_2)[i]$ are absolutely distinguishable. In the important special case of the absence of absolutely distinguishable symbols, anomalies of the first kind cannot exist. Therefore, the correctness condition is simplified to the absence of anomalies of the second kind. In this paper, it is shown that checking for the absence of anomalies of the second kind is reduced to checking for the absence of paths (starting at the selected vertex) of negative weight in the so-called automaton-square graph. This absence can be detected by the Bellman — Ford algorithm. The total complexity of checking for the absence of anomalies of the second kind is $O(|Q|^4|S|^2)$ in time and $O(|Q|^2|S|^2\ln|Q|\ln L\ln |S|)$ in memory, where $|Q|$ is the number of states of the automaton representing the function $\hat{F}$, $L$ is the maximum length of the word Alice throws out.

Détail

Keywords: covert channels, partial erasure channel, absolutely distinguishable characters, Bellman — Ford algorithm, checking of the absence of an anomaly of the second kind.

Bibliographie

[1] Kazakov I. B., “A validation algorithm of the transmitter`s boundedly deterministic behaviour in a partial erasure channel”, Prikladnaya Diskretnaya Matematika, 2023, no. 59, 88–110 (in Russian)

[2] Kazakov I. B., “Criterion for the existence of a consistent protocol in a partial erasure channel”, Chebyshevskiy Sbornik, 22:1 (2021), 133–151 (in Russian) | DOI | MR

[3] Kazakov I. B., “Reliabilty criterion for channels with prohibitions”, Intellektual'nye Sistemy. Teoriya i Prilozheniya, 22:2 (2019), 33–55 (in Russian) | MR

[4] Kazakov I. B., “Transmission of information in channels specified by structures of partial erasure. P. 1”, Programmnaya Inzheneriya, 11:5 (2020), 277–284 (in Russian)

[5] Kazakov I. B., “Transmission of information in channels specified by structures of partial erasure. P. 2”, Programmnaya Inzheneriya, 11:6 (2020), 322–329 (in Russian)

[6] Bellman R. E., “On a routing problem”, Quarterly Appl. Math., 16 (1958), 87–90 | DOI | MR

[7] Cormen T. H., Leiserson C. E., Rivest R. L., and Stein C., Introduction to Algoritms, 2nd ed., MIT Press and McGraw-Hill, Massachusetts, 2001, 1203 pp. | MR