PROBLEMS OF INFORMATION TRANSMISSION
A translation of Problemy Peredachi Informatsii

CONTENTS                  

On Constructions of Regular Hadamard Matrices and Bent Functions
J. Rifà, M. Villanueva, D. V. Zinoviev, and V. A. Zinoviev
pp. 273–290

Abstract—Using the generalized Kronecker construction from two binary Hadamard matrices, we build new families of Hadamard matrices of square order, which keep many properties of the original matrices. Specifically, when one of the initial matrices is the Sylvester Hadamard matrix, the resulting Hadamard matrix is regular and has a bent function in each row or in each column. These bent functions belong to the Maiorana–McFarland class. When both initial Hadamard matrices are Sylvester Hadamard, regular Hadamard matrices having a bent function in each row and column are obtained. In this case, we can construct bent functions with maximal algebraic degree. Moreover, we are able to compute the dimension of the kernel and an upper bound for the rank. Finally, we give two specific constructions using Latin squares.

A Transformation Preserving the Dimension and Minimum Weight of Cyclic Codes
Ryul Kim and Un Ye Kim
pp. 291–303

Abstract—Cyclic codes are an important subclass of linear codes and have been extensively studied due to their wide applications. Many classes of optimal ternary and quinary cyclic codes were constructed in the recent literature. However, some cyclic codes of different generator polynomials may have the same optimality. In this paper, we investigate when the cyclic codes of the same length have the same optimality. We consider a transformation preserving the dimension and minimum weight between $p$-ary cyclic codes of the same length. In addition, three optimal quinary cyclic codes $C_{(1,e,t)}$ with parameters $[5^m-1,5^m-2m-2,4]$ are presented, where $t=(5^m-1)/4$.

Design of Polar Codes with Large Kernels
P. V. Trifonov and G. A. Trofimiuk
pp. 304–326

Abstract—Design techniques for polar (sub)codes with large kernels are presented for the case of the binary input AWGN channel. Namely, methods are presented to estimate the capacities and Bhattacharyya parameters of the bit subchannels induced by a large kernel polarizing transformation. Upper and lower bounds relating the capacity and Bhattacharyya parameter of a channel are used to refine the obtained estimates. Furthermore, a method for finding an optimal kernel sequence in mixed-kernel polar codes is presented. The proposed approach can be immediately used to construct polar codes for the Rayleigh fading channel.

Modeling of Preemptive Channel Access in Wi-Fi Networks
A. V. Riterman, D. V. Bankov, A. I. Lyakhov, and E. M. Khorov
pp. 327–343

Abstract—To ensure reliable, low-latency packet delivery required by real-time applications (RTAs), such as industrial applications, it is planned to introduce the preemptive channel access method in a new amendment to the Wi-Fi 8 standard. This access method is novel for Wi-Fi networks, so the actual task is to tune its parameters to fulfill the requirements for the quality of service of RTA traffic and increase the network throughput. In order to solve this problem, we have developed a model of a Wi-Fi 8 network, which helps to find how the RTA frame delay quantile and the efficiency of channel utilization by the network access point depend on the RTA traffic intensity and parameters of the method. We explicitly find the parameters of the method that provide the required delay and reliability of RTA traffic delivery while maximizing the channel utilization efficiency.

Complexity-Preserving Transposition of Summing Algorithms: A Data Flow Graph Approach
D. V. Polevoy, D. D. Kazimirov, M. V. Chukalina, and D. P. Nikolaev
pp. 344–362

Abstract—This paper introduces a novel method for transposing summing algorithms, which eliminates the need for an explicit matrix representation of a direct summing operator. Unlike the approach previously proposed in the literature, which relies on decomposing the direct operator matrix into simpler factors, our method leverages a graph-based interpretation using directed acyclic graphs (DAGs). By focusing on the analysis of structure of the DAG associated with the summing algorithm, we avoid the complex and often cumbersome task of operator matrix factorization. The proposed method maintains the asymptotic computational efficiency of the original algorithm while offering a more accessible and flexible framework for transposition. In this paper, capabilities of graph interpretation are demonstrated by analyzing fast algorithms for computing forward and backward projection operators for a 2D low-angle reconstruction problem for circular-orbit parallel-beam CT. As a key component, these algorithms incorporate the transposition of classical fast Hough transform (HT) operators, including that realized by the Brady–Yong algorithm. Moreover, we apply the proposed transposition method to the novel $\mathit{FHT}2\mathit{DT}$ algorithm for fast and substantially accurate computation of the HT. The transposed $\mathit{revFHT}2\mathit{DT}$ algorithm offers a computationally efficient approach for calculating the transposed HT for images of arbitrary size. This overcomes the limitations of the transposed Brady–Yong algorithm, which is restricted to images with power-of-two widths.

Efficient In-Place Hough Transform Algorithm for Arbitrary Image Sizes
D. D. Kazimirov, D. P. Nikolaev, E. O. Rybakova, and A. P. Terekhin
pp. 363–391

Abstract—Nowadays, the Hough transform (HT) is a tool extensively used in image processing and computer vision. It finds applications ranging from line detection in images to tomographic reconstruction. Due to their numerous industrial applications, which comprise execution not only on remote servers but also on less powerful embedded devices and within the Internet of Things (IoT) paradigm, fast algorithms for computing the HT (fast HT, or FHT) that efficiently utilize computational memory are in high demand. In-place algorithms, which use memory allocated for the input data array and may employ a small amount of additional memory for intermediate calculations, are recognized to have such characteristics. For images with widths that are powers of two, such an algorithm is known; it is the in-place version of the de facto standard Brady–Yong algorithm. However, in practice, it is often needed to compute the FHT for images with arbitrary widths, to which the Brady–Yong algorithm is not applicable. In this paper, we propose an in-place $\mathit{FHT}2\mathit{IDS}$ algorithm. It is a~modification of the $\mathit{FHT}2\mathit{DS}$ out-of-place algorithm for computing the FHT for images of arbitrary width previously presented in the literature. We justify correctness of the $\mathit{FHT}2\mathit{IDS}$ algorithm and show that the result of processing an image of an arbitrary width matches the output of the $\mathit{FHT}2\mathit{DS}$ algorithm. We demonstrate that the $\mathit{FHT}2\mathit{IDS}$ algorithm allocates a significantly smaller data array at each recursion step compared to the $\mathit{FHT}2\mathit{DS}$ algorithm: at each recursion step, it requires an array of size no greater than $w+h$, rather than $wh$, assuming that the input image has a $w\times h$ shape. We also develop a nonrecursive version of the $\mathit{FHT}2\mathit{IDS}$ algorithm, which is called the $\mathit{FHT}2\mathit{IDS}$-$\mathit{NonRecursive}$ algorithm. The auxiliary space complexity of the $\mathit{FHT}2\mathit{IDS}$-$\mathit{NonRecursive}$ algorithm is proved to be $\mathcal{O}(w+h)$, while the $\mathit{FHT}2\mathit{DS}$-$\mathit{NonRecursive}$ algorithm, a nonrecursive version of the $\mathit{FHT}2\mathit{DS}$ algorithm, demonstrates the auxiliary space complexity of $\mathcal{O}(wh)$, where $w$ and $h$ denote the dimensions of the input image. Experimental results show that the $\mathit{FHT}2\mathit{IDS}$-$\mathit{NonRecursive}$ algorithm implemented in C/C++ is 45% faster than its out-of-place counterpart, $\mathit{FHT}2\mathit{DS}$-$\mathit{NonRecursive}$. The $\mathit{FHT}2\mathit{IDS}$ and $\mathit{FHT}2\mathit{IDS}$-$\mathit{NonRecursive}$ algorithms are also implemented in Python within an open-access adrt library, which the readers may find useful in their research.