1. Introduction

Conventional methods of correcting errors in control systems are faced with the following dilemma: on the one hand, the use of sophisticated coding structures like turbo codes or low-density parity-check codes, despite their efficiency in telecommunication systems, is unacceptable in real-time systems due to the computational delays involved [1, 2]. On the other hand, the use of relatively short codes is unable to fully exploit the error correction potential of these codes with classical decoding methods [3]. The method of permutation decoding seems to be a promising approach that can overcome these limitations while utilizing the benefits of the available soft decision information and iterative transformations [4, 5].

Another important feature of permutation decoders is the ability to pre-compute all possible symbol permutations for code vectors [11]. This feature enables the replacement of complex mathematical operations with lookup tables based on a pre-computed cognitive map, thus greatly increasing the speed of the overall decoding process [12]. However, the methodological basis for the design of cognitive maps for moderate-length redundant codes is an area that is not sufficiently investigated [13].

In this paper, this gap is filled by providing general guidelines for the design of cognitive maps for block codes with lengths not exceeding 15 symbols. This is achieved through an in-depth analysis of the statistical properties of productive and unproductive permutations for Hamming and BCH codes, as well as identifying the orbital properties in the permutation space and the memory optimization potential through orbit representations. The implementation is based on a Python program for comprehensive analysis and providing quantitative guidelines for decoder design.

2. Theoretical Framework

2.1 Orbit Representation

Among the concepts that have been brought by algebraic group theory is that of a permutation of a cyclic nature, which is referred to as an orbit [6]. In this regard, cyclic permutations constitute a closed set, as they are similar in structural features. Such concept can be especially applicable to memory compression, since the permutations in a given orbit can be represented only in terms of the combinations to make such an orbit representation (OCO) [7]. The code dimension is equal to the length of the orbit and this is denoted by k , Consequently, when permutations are represented in a single orbit the theoretical memory demand can be cut down by a factor of k [8].

3. Methodology

3.1 Research Approach

A systematic computational framework is adopted by the study in order to investigate the overall permutation space of some chosen block codes. In specific, three codes were considered by the study:

1. The (7,4,3) Hamming code, which was considered as a reference code
2. The BCH code of parameters (15,7,5), which was considered for its relatively moderate length and optimal redundancy
3. The BCH code of parameters (15,5,7), which was considered for its improved error correction capability

These codes were considered by the study based on the rationale that they possess parameters closely matching the optimal relationship , which reflects an efficient balance of redundancy and error correction capability.

3.2 Software Implementation

A Python program was designed to exhaustively explore all possible symbol permutations.

3.3 Experimental Procedure

The analysis process involved a number of sequential steps:

1. Generation Phase: Combinations of positions were produced using all possible combinations, .
2. Classification Phase: Combinations were analyzed for non-singularity in the information matrix.
3. Orbit Identification: Cyclic orbits were determined among the productive combinations.
4. Statistical Analysis: Quantitative analysis was performed for each code.
5. Validation: Results were validated against theoretical predictions.

4. Results and Discussion

4.1 Hamming Code (7,4,3) Analysis

The Hamming code was adopted as a validation case because of its relatively smaller permutation space complexity. Table 1 lists all productive permutations for this code.

Table 1

Analysis results for different codes

Table 2

OCOs starting with position 1

Analysis showed that out of 35 possible combinations, 28 were productive (80 %), while 7 were unproductive (20 %). Unproductive permutations refer to those situations where the information sub-matrix is singular, thus rendering it impossible to develop a valid equivalent code.

Analysis of the orbit resulted in five unique orbits, where each orbit contained permutations. Table 3 shows all possible orbit structures.

Table 3

Orbit structure for Hamming (7,4,3) code

*Orbit 5 is _italicized_ and comprises all unproductive permutations, where the determinant is zero.

Most noteworthy is that Orbit 5 comprises only unproductive permutations, thus showing that unproductive combinations have inherent cyclic structures. This is quite significant, thus showing that there is a possibility of using correction methods within unproductive orbits.

4.2 BCH Code (15,7,5) Analysis

For the (15,7,5) BCH code, the initial sample space contains combinations. Table 4 shows the sample membership in generating orbit combinations.

After removing duplicate permutations within each orbit, the sample size is reduced to 3003 combinations, which reflects a 54 % reduction. This validates the memory savings potential of employing an orbit representation method.

Further filtering to remove combinations with zero determinant values resulted in an additional 1,491 combinations being removed, leaving 1512 productive generating combinations. Figure 1 shows this filtering process.

Table 4

Sample OCO membership for (15,7,5) code

Fig 1. Progressive filtering of (15,7,5) code permutations

4.3 BCH Code (15,5,7) Analysis

The (15,5,7) code was selected due to its superior error correction capabilities. Table 5 shows a sampling of OCO membership.

Table 5

Sample OCO membership for (15,5,7) code

From an original 3003 combinations, orbit reduction resulted in 1001 generating combinations, a reduction of 66 %. Determinant filtering then reduced it further to 616 productive combinations. Table 6 summarizes the results of the filtering for both BCH codes.

Table 6

Volume reduction summary for BCH codes

4.4 Statistical Distribution Analysis

Figure 2 shows a graphical representation of the distribution of productive and unproductive combinations for all three codes.

Fig. 2. Productive vs unproductive permutation ratios

Some important trends are observed in the data:

1. Productivity Ratio Decreases with Code Length: For the shorter code (7,4), the productivity ratio is 80 %. For the longer codes, this ratio drops significantly, reaching about 47 % for the (15,7) code, out of the OCOs, while for the (15,5) code, the ratio is about 61 %. This is because the probability of singular submatrices increases with the dimensionality of the codes
2. Orbit Structure Efficiency: The amount of memory reduced using the orbit structure is exactly the code dimension , as expected from the theory. For example, in the case of the (15,7) code, with , the amount of memory reduced is exactly 7 times, while in the case of the (15,5) code, with , the amount reduced is exactly 5 times [6, 7, 8].
3. Determinant Filtering Impact: The determinant filtering process removes about 50 % of the combinations in the case of the (15,7) code, while in the case of the (15,5) code, about 38 % are removed, i.e., the combinations in which the information submatrix is singular, despite the cyclically distinct positions.

4.5 Memory Requirements Analysis

Table 7 shows the memory requirements for the storage of the cognitive map using the proposed representation strategies.

Table 7

Memory requirements comparison

*Estimated for complete matrix storage including all permutations.

It is evident from the table that the significant reduction in the case of longer codes justifies the need for the orbit-based strategy [6, 7]. The storage of the entire matrix for the (15,7,5) code would require about 11.15 terabytes, which is clearly impractical for embedded systems, while the orbit-based strategy makes the storage requirement a list of manageable values.

It is evident from Figure 3 that the orbit-based strategy offers significant memory savings. For the (15,7,5) code, the initial requirement of 6435 combinations is reduced to 3003 after orbit identification, followed by a further reduction of 50 % using the determinant filter, resulting in a total reduction of 76.5 %. Figure 3 shows the final count of productive generating combinations available for decoder implementation.

Fig. 3. Memory reduction Analysis

4.6 Orbital Properties and Practical Implications

A particularly interesting property that is revealed by the analysis is related to the initial element of the generation of the combinations of the orbit [6]. Table 8 verifies this observation.

Table 8

First element statistics for OCOs

Productive generating orbit combinations all start in symbol position 1. This observation has a significant impact upon the search process in the decoding process because it allows a reduction in search space by a factor of .

4.7 Derivative Combinations

Each combination in a generating orbit has the potential to produce a number of derivative combinations due to cyclic shifts [7]. Table 9 verifies this potential.

From a practical standpoint, this means that by storing a set of generating orbit combinations, a much larger set of combinations is made available to us, and this by a multiplicative factor equal to our dimension .

Table 9

Derivative combination potential

5. Discussion

5.1 Practical Applications

The results have important practical implications for applying and implementing permutation decoders:

1. Optimization of memory usage: Cognitive maps can be achieved through simple generation of orbit combinations, thus achieving a k-fold optimization of memory usage without compromising system capabilities [6, 7, 9].
2. Speedup of search procedures: The observation that all productive OCOs start from position 1 provides a basis for using specific search procedures for speeding up the search [6, 10].
3. Improvements in error correction procedures: Understanding the structure of unproductive orbits provides a basis for developing correction procedures that transform unproductive permutations into productive ones by making only minor changes in symbols [11, 12].
4. Scalability of decoders: The proposed method is applicable for code lengths up to 15 [13, 14]. However, for longer lengths, a combinatorial explosion requires alternative optimization techniques [15].

6. Conclusions

This article undertakes an exhaustive statistical investigation of the permutation space of short block codes relevant to the control system domain. The key results of the investigation are as follows:

1. Validation of Orbital Structure: Permutations are naturally grouped into cyclic sets called orbits. The size of the orbit is equivalent to the dimension of the code, denoted by . This property lends itself to a k-fold reduction of the memory requirements for storing the cognitive maps [6, 7].
2. Productivity of Permutations: In the case of the (7, 4, 3) Hamming code, 80 % of the permutations are found to be productive. In the case of the (15, 7, 5) BCH block code, approximately 47 % of the generating combinations are found to be productive. In the case of the (15, 5, 7) block code, approximately 61 % of the generating combinations are found to be productive.
3. Optimization of Memory Requirement: The data is represented using the orbit structure of the permutations. The memory requirement is reduced by 54–66 % prior to the determinant filter. It is reduced by 76–79 % after the determinant filter [6, 7, 8].
4. Regularity of Structure: Productive combinations of the generating orbit combinations are found to start from the first position. This makes the search process easier.
5. Derivative Potential of the Permutations: The generating combinations of the permutations are found to have derivative combinations. Using this property of the permutations, 3080–10584 permutations are accessible from compact storage.

References:

1. Ganin D. V., Damdam M. A. Ya., Savkin A. L. Permutation decoding in low-power wireless sensor networks. Avtomatizatsiya protsessov upravleniya, 2022, no. 2 (68), pp. 37–44.

2. Sklyar B. Digital communication. Theoretical foundations and practical application. Moscow: Williams, 2003. 1104 p.

3. Morelos-Zaragoza R. The Art of error-correcting coding. Moscow: Technosphere, 2005. 320 p.

4. Peterson W., Weldon E. Error-correcting codes. Moscow: Mir, 1976. 594 p.

5. Adzhemov A. S., Sannikov V. G. General theory of communication. Moscow: Hotline-Telecom, 2018. 624 p.

6. Fried E. Elementary introduction to abstract algebra. Moscow: Mir, 1979. 260 p.

7. Babanov N.Yu., Shakhtanov S. V. Cyclic properties of permutation orbits of the cognitive map of a permutation decoder for real-time systems. Proektirovanie i tekhnologiya elektronnykh sredstv, 2020, no. 4 (62), pp. 85–92.

8. Nichunaev A. A., Brynza A. A., Gladkikh A. A., Savkin A. L., Lyutvinskaya P. B. Structure and interrelation of cognitive indicators in the permutation decoding system. Avtomatizatsiya protsessov upravleniya, 2023, no. 4 (74), pp. 126–133.

9. Gladkikh A. A. Fundamentals of the theory of soft decoding of redundant codes in an erasure channel. Ulyanovsk: UlSTU, 2010. 379 p.

10. Babanov N.Yu., Gladkikh A. A., Namestnikov S. M., Shakhtanov S. V. Properties of cyclic structures in the system of permutation decoding of redundant codes. Avtomatizatsiya protsessov upravleniya, 2020, no. 2 (60), pp. 82–89.

11. Gladkikh A. A., Ovinnikov A. A., Tamrazyan G. M. Mathematical model of a cognitive permutation decoder. Tsifrovaya obrabotka signalov, 2019, no. 1, pp. 14–19.

12. Gladkikh A. A., Ovinnikov A. A., Pchelin N. A., Brynza A. P. Permutation decoding with a system of adapted alternative solutions. Tsifrovaya obrabotka signalov, 2023, no. 4, pp. 73–78.

13. Attaby A. L. Kh., Brynza A. A., Ganin D. V., Nichunaev A. A., Novoselov A. V. Evaluation of statistical characteristics of a permutation decoder by the method of its software implementation. Avtomatizatsiya protsessov upravleniya, 2023, no. 2 (72), pp. 91–98.

14. Yue C., Miloslavskaya V., Shirvanimoghaddam M., Vucetic B., Li Y. Efficient Decoders for Short Block Length Codes in 6G URLLC. arXiv:2206.09572v2 [cs.IT], 2022.

15. Gladkikh A. A., Chilikhin N.Yu., Klimov R. V. Methods of efficient decoding of redundant codes and their modern applications. Ulyanovsk: UlSTU, 2016. 258 p.