PROBLEMS OF INFORMATION TRANSMISSION
A translation of Problemy Peredachi Informatsii

CONTENTS                  

On Nonlinear 1-Quasi-perfect Codes and Their Structural Properties
A. M. Romanov
pp. 141–154

Abstract—We consider nonlinear quasi-perfect codes with packing radius 1 over a finite field of $q$ elements. We call these codes nonlinear 1-quasi-perfect $q$-ary codes. We study the structural properties of nonlinear 1-quasi-perfect $q$-ary codes, namely the rank and the dimension of the kernel. We prove that for $n=q^m$ and any $t\in\{1,2,\ldots,m+1\}$ there exist nonlinear 1-quasi-perfect $q$-ary codes of length $n$ and rank $n-m-1+t$. Here, $m\ge 5$ for $q=3$ and $4$, $m\ge 4$ for $5\le q\le 19$, and $m\ge 3$ for $q\ge 23$. In particular, we prove that there exist full-rank nonlinear 1-quasi-perfect $q$-ary codes. Also, for some nonlinear 1-quasi-perfect $q$-ary codes we calculate the kernel dimension.

On Additive Quasi-abelian Codes over Finite Fields and Their Duality Properties
S. Sharma, M. Yadav, and A. Sharma
pp. 155–188

Abstract—In this paper, we introduce and study a new class of additive codes over finite fields, viz. additive quasi-abelian (QA) codes, which is an extension of (linear) quasi-abelian codes over finite fields. We study algebraic structures of these codes and their dual codes with respect to ordinary and Hermitian trace bilinear forms. We further express these codes as direct sums of additive codes over finite fields and derive necessary and sufficient conditions under which an additive QA code is (i) self-orthogonal, (ii) self-dual, and (iii) an additive code with complementary dual (or an ACD code). We also derive necessary and sufficient conditions for the existence of a self-dual additive QA code over a finite field. Besides this, we obtain explicit enumeration formulas for all self-orthogonal, self-dual, and ACD additive QA codes over finite fields. We also list several MDS and almost MDS codes belonging to the family of additive QA codes.

An Update on Optimal $(v,4,1)$ Binary Cyclically Permutable Constant Weight Codes and Cyclic $2$-$(v,4,1)$ Designs with Small $v$
T. Baicheva and S. Topalova
pp. 189–198

Abstract—We construct new $(v,4,1)$ binary cyclically permutable constant weight (CPCW) codes with lengths $v\le 136$. We establish that (due to a software error) $85\,285$ ($0.0044\%$) of all the $1\,939\,771\,399$ binary $(v,4,1)$ CPCW codes with $v\le 76$ were not obtained in our paper “Classification of Optimal $(v,4,1)$ Binary Cyclically Permutable Constant Weight Codes and Cyclic $2$-$(v,4,1)$ Designs with $v\le 76$”, Probl. Inf. Transm., 2011, vol. 47, no. 3, pp. 224–231. We now correct the number of codes for lengths $41$, $46$, $53$, $58$, $71$, $73$, and $74$, wrongly given in our 2011 paper, and add the previously missing $85\,285$ codes to the results available online. Our attempt to classify $(v,4,1)$ binary CPCW codes with $v>76$ leads to an extremely big number of codes, which makes the classification practically unusable. When $v=12n+1$, the number of codes is relatively smaller, and they correspond to $(v,4,1)$ cyclic difference families and to cyclic $2$-$(v,4,1)$ designs, which have various other relations and applications. Cyclic designs with one short orbit can be constructed for $v=12n+4$. By a parallel algorithm run on the Bulgarian high performance computer Avitohol, we obtain classification results for optimal $(85,4,1)$ CPCW codes (cyclic $2$-$(85,4,1)$ designs) and for cyclic $2$-$(88,4,1)$ designs. For all other $76\lt v\le 136$, we do not construct all $(v,4,1)$ CPCW codes but provide files with thousands of new optimal codes such that each of them differs in many codewords from most of the other codes.

Reducing the Complexity of the Layer Scheduled LDPC Decoder Based on the Information Bottleneck Method
I. A. Melnikov, A. Yu. Uglovskii, A. A. Kreshchuk, A. A. Kureev, and E. M. Khorov
pp. 199–208

Abstract—The complexity of belief propagation algorithms for decoding LDPC codes can be significantly reduced by storing the precomputed sum of messages in variable nodes. This optimization is particularly useful for layered schedule decoders, where it also simplifies the hardware implementation. To reduce the requirement for the amount of information to be processed during decoding, the information bottleneck method is used, which reduces the bit width of all updated messages. However, under this approach, re-calculation of the sum when excluding one of messages becomes complicated. The paper is devoted to development of an algorithm for construction of a discrete binary function corresponding to such subtraction. When using this algorithm, the number of stored and used lookup tables for variable nodes is reduced.

On Universality of Regular Realizability Problems
A. A. Rubtsov and M. N. Vyalyi
pp. 209–232

Abstract—We prove the universality of the regular realizability problem for several classes of filters. These filters are descriptions of finite relations on the set of nonnegative integers in the format proposed by P. Wolf and H. Fernau. The universality is proved with respect to the disjunctive reduction in polynomial time for unary relations and in polynomial space for invariant binary relations. The necessity of stronger reductions corresponds to the results of Wolf and Fernau on the decidability of regular realizability problems for many algorithmic problems in graph theory.

Performance Evaluation of Wi-Fi 7 Networks with Restricted Target Wake Time
D. V. Bankov, A. I. Lyakhov, E. A. Stepanova, and E. M. Khorov
pp. 233–254

Abstract—We study a most recent mechanism for reserving channel resources to deliver high-priority traffic in Wi-Fi networks, Restricted Target Wake Time (R-TWT). We develop an analytical model of a Wi-Fi network using the R-TWT mechanism, which allows us to estimate the throughput of users transmitting low-priority traffic, depending on the R-TWT reservation period, restrictions on the size of transmitted frames and modulation and coding schemes used. The model shows that the dependence of the user throughput on the R-TWT period is not monotonic, and a slight increase in the R-TWT period can lead to both an increase and a significant drop in the user throughput.

Closed-Form Approximations for the URLLC Capacity Using $G/G/s$ Queues
A. Yu. Karamyshev, E. D. Porai, and E. M. Khorov
pp. 255–272

Abstract—Efficient operation of resource management algorithms in modern ultra-reliable low-latency communication (URLLC) systems requires fast and accurate estimation of the system capacity, i.e., the maximum traffic volume per second that can be served under strict quality of service requirements such as low latency and high reliability of data delivery. Queueing theory is helpful in this task; however, due to the variability of communication systems and their operating conditions, queueing theory has to operate with general distributions, i.e., to consider $G/G/s$ queues. For such queues, obtaining a precise analytical solution is either impossible in a closed-form or computationally expensive, so approximations for $G/G/s$ models are in demand. However, existing approximation methods fail to account for URLLC features: low (but nonzero) delay thresholds and low probabilities of exceeding these thresholds, which results in significant errors in capacity estimation. We propose and investigate closed-form approximation formulas for estimating the URLLC capacity using $G/G/s$ queues. We analyze the accuracy of the proposed formulas and distinguish regions of acceptable capacity estimation errors. Finally, we show a specific asymptotics for the URLLC system capacity in a wide range of parameters and scenarios.