In the following paper we provide analysis on testing procedure and development of software models, and application architecture for investigation of error-correcting codes' parameters and decoding algorithms. The proposed models can be applied for the development of software for decoding Turbo-Product Codes (TPC). They allow simplifying development process and retrieve universal solution for TPC investigation. The models are described in the Unified Modeling Language (UML) and follow design pattern recommendations. They can be used for software implementation in various programming languages that support object-oriented model. Heatmap visualization tool is supposed to be the main part for visual investigation of the decoding process. In this work, we propose metrics for heatmap organization and explained behavior of the cells to deliver comprehensible presentation of the message state during decoding process. The combination of metric and heatmap component provides effective way to observe impact of each decoding algorithm element on the process and gives abundant information for comparative analysis about algorithm improvements.
Telecommunication systems are complex systems that includes various set of
components on the different levels. One of the substantial parts is coding systems where
errorcorrecting codes (ECC) are heavily utilized [
The problem of investigation of ECCs’ parameters is one of the most important issues to achieve better performance of the system. Different codes reveal different characteristics under changeable conditions. Even slight optimization might be critical for the realization of the final system. It also should be mentioned that it requires much time to meticulously check combination of parameters of the code, compare different codes with each other, and select the most suitable code according to the expected properties.
The first testing stage is usually performed on software level as it takes minimum time to verify proof-of-concept. Testing on hardware level implies actual implementation of the device that can be insufficient. However, available software solutions either provide only limited functionality without possibility to change coding parameters or requires payment for the software usage. Consequently, there is a lack of software that provide flexibility in configuration of the code and decoding algorithms.
Decoding algorithms are the cornerstone of the coding level in telecommunication systems as throughput as well as complexity are directly connected with them. Their implementation requires execution immense number of computational operations.
Testing of the ECC is concerned with processing tremendous amount of data. Input message, intermediate results, decoding results, computations performed according to the algorithm form the list of the most important information required to investigate decoding performance. It is important to observe transitions inside the message and conclude how each part of the algorithm makes impact on the decoding process and whether it can be improved.
In this paper, we propose architecture and models for development of software that assists in investigation of ECC and respective decoding methods. The proposed software models are supposed to be extensible in terms of adding new codes or decoding algorithms. The software is designed to work with block ECC but can be improved by adding support of convolutional codes. 2
Analysis of Scientific Sources and Software Solutions
Software decoding of ECC is represented by several well-known software packages
and libraries [
Before considering ECC software itself, it is worth to mention that various ECCs are
employed in the modern electronic applications. Two most popular fields are data
transmission and data storage. However, some of the codes are preferable due to the
characteristics they demonstrate. The most important parameter of ECC is error-correcting
ability that strongly depends on the procedure of decoding and data representation.
Another significant parameter is throughput. Once again, typically, it depends on the
number of operations in the decoding algorithm, their complexity, and suitability for
parallelization. The following group of the ECCs stands out among the others according to
their involvement in different technologies and their main properties:
Low-Density Parity Check (LDPC) codes (have high correction ability, suitable for
complex systems) [
In this work, we are investigating software development for TPC-decoding system.
Therefore, it is worth mentioning that many decoding algorithms can be applied to
process TPC. Chase, Chase-Pyndiah [
Matlab [
A Fast Forward Error Correction Toolbox or AFF3CT [
Other software libraries for ECC investigation like [
Companies specialized in ECC-development provide their own software and
hardware implementation [
The codes can be applied in various industrial application [
The vital point for decoding software is comprehensible visual presentation of data. Heatmap is a special type of diagram that is very convenient for visual representation of quantitative data in form of matrix. Because of that factor, we selected heatmap as main component for data presentation.
In the paper we investigate modelling of the decoding process for implementation in
software, provide software models for the further software realization. We also provide
detail on data presentation in software in the form of heatmap. The established software
models are intended to be used in the software development process for investigation
of TPC-decoding and other ECCs. We apply experience and results attained in the work
[
Typically, the following stages are an obligatory to model signal transmission over network: 1. Encoding. 2. Transmission over the noise channel. 3. Decoding received message.
Depending on the detalization level of a system, a few additional stages (scrambling, interleaving, modulation, manipulation, etc.). However, those abovementioned three stages are the basis for investigation.
At the encoding stage, the input message is processed with encoding algorithm (multiplication of each component on corresponding generation matrix in case of TPC). Consequently, the message is altered with new information that assists in error correction at the decoding stage. The message for transmission at this stage is considered as a set of binary data.
Data transmission stage is intended to model influence of noise to the signal. As a result of this stage, errors appear in the transmitted signal. Moreover, due to performance reasons, each bit in the data is presented as soft value with limited quantization (for frugal memory consumption), e.g. it can be range [-3; 3] for case of 3-bit representation.
Decoding stage plays utmost important role in the system. It performs processing on the message according to the decoding algorithm and outputs actual data for further usage once again in the form of binary message without redundancy data. In the most cases, decoding algorithm is applied several time to the message. Number of iteration is restricted. The results of each iteration are featured by the message state and decoding algorithm’s parameters. Additionally, knowledge of the initial message implies that we can gain an advantage of directly comparing input and output of the system.
After the performed analysis, we can identify main entities for the software decoding system: message; decoding results; decoding algorithm; decoding system.
First, we propose the following workflow for researcher who works with software. The workflow is illustrated in Fig. 1 in form of Unified Modelling Language (UML) activity diagram. The user sets decoding parameters and launches decoding process. When the results of the decoding are available, analysis stage begins. That actually means work with user interface and finish of the decoding process itself. However, single run of the main cycle gives results only for one code. Comparison of several algorithms is more effective procedure for investigation and selection of better approach. One of peculiarities of TPC is that single decoding iteration is divided on two half-iterations. First, the message is processed in one dimension (e.g. rows) and then takes place processing in other dimension. Row decoding affects column decoding and column decoding affects row decoding. Thus, it is necessary to grant user option to store results of both half-iterations (one of them matches final iteration results).
Let us further introduce class infrastructure for the software that is illustrated in Fig. 2. The class with corresponding name represents decoding algorithm. It is an abstract class that serves as a parent class for other classes that actually provide algorithm implementation. Hence, presence of multiple algorithm is supposed by the system design. It follows instruction for the Strategy design pattern which means that user can easily switch from one decoding algorithm to another. Regarding benefits of class parametrization, decoding algorithm classes may also be parameterized. In this case, only single decode method should have type parameter. However, due to the extension reasons, new method or even whole class may become parameterized. Another important peculiarity of the TPC-decoding is that hardware implementation is performed for the algorithms that make use of limited precision in number representation. Typically, operations with integer operands are more preferable. Thus, it is important to observe results yielded by algorithm with different precision in number representation. For that purpose, decoding classes may be parameterized with type for number representation.
From this point of view, we can deduce that several instances of the same class can be present with different type parameter. Creation of the corresponding class instances is a task instance of class that implements Factory design pattern. As the user selects new decoding algorithm to explore, the appropriate call is directed to factory objected. However, it will not be efficient usage of resources if the requested instances has been created previously. Therefore, the factory object should also manage internal algorithm pool object where they are stored. If the requested object is available in the pool, it is passed back to the caller. Otherwise, factory creates it and stores it into the pool immediately. This part of the software model follows instructions of the Object pool design pattern. The corresponding class diagram is demonstrated in Fig. 3. Several options are available to retrieve data for testing: 1. Actual channel data stored in the file. This is the simplest variant, as it only requires reading data from the file. It is also a convenient way to check performance two different decoders on the same data and compare their performance with each other. 2. Simulate transmission process over the noisy channel. This option is much closer to the real world functioning of the system. It begins with reading data to encode from file or generating random data for this purpose. The data are altered “on the fly” according to noisy channel’s parameters. More computational operations are required for the simulation then simple reading from file.
Thus, we can identify more artifacts for the application. The first one is data loader that
executes load of data from the specified source. The loader is aware that there are two
cases for reading data (raw not encoded data, transmitted data). The second artifact is a
channel simulator. Main responsibility of the simulator is to apply noise or other
channel impact to the encoded data. The relations between mentioned classes are depicted
in Fig. 4.
One of the most significant features of decoding software is possibility to analyze
decoding results and compare outputs of different algorithms. To collect information on
the decoding results we propose usage of an Observer pattern. Classes connected with
decoding should be able to issue notification about the end of each half-iteration and
expose necessary information to the interested observing instances. As notification is
sent, observer retrieves information and stores it into the list. Each data chunk can be
wrapped into instance of class for storing data to distinguish this information from the
original message. Additionally, it provides comprehensible way to control change
history of the message under processing. This option is very helpful for user interface
implementation because demonstration of changes requires simple traversing over the
list with stored instances. The classes for implementation of result storage and review
functions are shown in Fig. 5.
All the models proposed in this paper have been developed using Bouml modeling
software [
Visual data representation of the decoding results is an actual feature for the decoding software. In opposite to well-known metrics for ECC system efficiency, it gives more details on how decoding algorithm deals with message information. Such lowlevel information also provides an opportunity to optimize algorithm by tuning parameters or specific decoding operations. As encoded message for TPC is a matrix of numbers, it is handful to represent it in form of heatmap. Each cell in the heatmap corresponds to the actual value in the message. Because heatmap applies color to the values, it is easier for the user to identify error patterns in the message, overview general message state, etc. Heatmap is also an effective tool to observe changes happened on the different iterations. As has been stated before, heatmap assigns specific color to each value. Straightforward usage of the numeric values to form color map gives no additional information and is hard to analyze. This implies that additional metric is necessary to form heatmap. Providing that initial message is known, we can infer message state at the very start of transmission. We assume that this is the desired state for output message. The numerical value si, j corresponding to each bit takes either maximum value max s or minimum value mins in the interval [ max s , mins ] in the start message. Value di, j in the decoded message takes value from the very same interval [ max s , mins ] but it does not necessarily need to be equal to max s or mins . Being aware of two values the for bit representation, we can devise metric that expresses difference between desired and actual values mi, j | si, j di, j | . (1) The metric can have only non-negative values. The lower metric, the better value di, j matches to the desired value. In fact, when mi, j 0 it means that decoding converged i, j bit to the correct value. The maximum value that can be assigned to the metric is if mmax is even and if mmax is odd.
hi, j 11sign(di, j ) bi, j mmax
2 bi, j mmax 1
2
It clearly states that the sign in the decoded value di, j has been changed due to large bias value bi, j . Sign transition in the heatmap should be marked by color for ease of visual interpretation.
Besides metric for each bit in the message, it is also convenient to have an aggregate metric that represents state of row or column of the message. Let us use Tri to denote aggregate metric for i row and Tcj to denote metric for j column. Their values are calculated as
Tri bi, j ,
j mmax | max s | | mins | .
If some bit position gets mmax metric value, that identifies decoding for bit finished with absolutely wrong value. Let us assume that final binary decoded value is identified according to the sign of the associated numerical value, e.g. where sign – function that returns -1 or +1 depending on sign of input parameter. Small bias from the target value does not end up with wrong decision about binary value in this case. Thus, on a heatmap we should clearly distinguish erroneous positions from correct ones. In most cases, we can identify error if the following condition is satisfied (2) (3) (4) (5) (6) Obviously, minimum value for the metrics is zero. The maximum value reaches mmax multiplied by the number of elements in the corresponding dimension. Therefore, range of possible values for the metrics is much larger than for individual bit. The color scale for aggregate metrics presentation should not contradict with general style of heatmap.
Regarding colors selection for heatmap, we may conclude with next statement. Two colors have to be selected to denote absence of bias and maximum level of bias (e.g. green and red are an essential choice). Errors in the decoded message should be easily recognizable. That means that transition from acceptable bias value (no error) to erroneous one in context of color presentation should not be smooth but rather stiff.
In the Fig. 6 illustration of the proposed approach to visual organization of heatmap
is shown for TPC constructed of (7, 4) Hamming codes with di, j takes value within
range [
1 0 0 0 2 3 3 0 0 1 1 1 1 1 0 0 0 1 2 3 3 0 0 0 1 0 1 1 2 0 0 0 1 1 1 0 0 1 0 0 1 1 0 0 1 1 1 1 1 Each cell contains its metric mi, j in the center. The higher value of metric, the darker background color. We can easily identify erroneous bits by the background. This example uses short codes. In case of long codes, it is feasible to make optional metrics display inside the cell.
The system has been implemented using JavaScript programming language and
React library [
The authors are looking forward to cooperation with other researchers and developers who are interested in the topic. We encourage everyone to contact us so the access to the code repository can be provided freely. Moreover, after investigation of the applicable software licenses for open-source projects and finalization of the application code, the decision about moving to the public domain is going to be made to disseminate findings of the presented paper and to facilitate further developments. 4
In the current paper, we present developed software models for ECC software design, specifically for software that deals with TPC. The software models leverage best practices of object-oriented programming to provide flexible solution for TPC investigation. The main advantage of the proposed model is that they take into consideration peculiarities of TPC-decoding process and support different option for accessing data on every stage of the decoding, comparing different algorithms, and different numerical data representation. The models represent workflow of the user actions, main classes that forms the whole decoding system, and supportive classes that are responsible for data loading, presentation, communication between classes, etc. The models can be used as a fundamental part for decoding software and have capability for further extension.