 Open Access
 Authors : Eduardo Valadez Campos , Jose Eduardo Mendoza Torres
 Paper ID : IJERTV10IS020233
 Volume & Issue : Volume 10, Issue 02 (February 2021)
 Published (First Online): 02032021
 ISSN (Online) : 22780181
 Publisher Name : IJERT
 License: This work is licensed under a Creative Commons Attribution 4.0 International License
Implementation of ReedSolomon Codes for Stratospheric Balloon Probes and NanoSatellites
Eduardo Valadez Campos Department of astrophysics Instituto Nacional de Astrofisica, Optica y Electronica
Puebla, Mexico
Jose Eduardo Mendoza Torres Department of astrophysics Instituto Nacional de Astrofisica, Optica y Electronica
Puebla, Mexico
Abstract The digital communications and data handling technics are essential in any system that require to store and transmit information from one point to another, and if the system has to work remotely, the software, as much as the hardware, is a key part when it comes to compensate errors in the data due to the environments with high electromagnetic noise, fluctuating power source or a changing visibility window to transmit. Usually, the purchase of a communication system with a sophisticated builtin Error Correction Codes (ECC) are quite expensive and, depending the country, always there is security restrictions. Therefore, in order to increase the performance of scientific data gathered from stratospheric balloon probes and nanosatellites using entirely lowcost commercial components, we develop a communication system to transmit/receive data files above 5KB with lowcost commercial RF transceivers, commercial ARMbased miniPC and using an implementation of ReedSolomon codes.
Keywords Tx; Rx; ReedSolomon Codes; Error Correcting Codes; ComponentsOffTheShelf; ARMbased; Galois field; codec.
1. INTRODUCTION
The use of ComponentsOffTheShelf or COTS based solutions has allowed to develop radioprobes, payloads and minisatellites with modern tools and a minimal cost that a couple decades ago, by getting full advantage of the economy of scale with cheap and plentiful components. Due to the typically shorter lifespan of these devices compared to traditional endeavors, it is possible to use newer, more innovative designs without running a high financial risk. This is interesting as it allows for rapid development and advancement in an otherwise conservative industry where only the large companies and agencies could afford such developments [1][2].
However, in order to increase the reliability of the COTS based devices, it is necessary to make thoroughly analysis of the environment conditions where the devices are going to operate and to replicate such conditions. Then, identify the weak points where the device shows poor performance or a risk of failure, so the development team can improve/replace/optimize such features [3].
When it comes down to data gathering, the performance improvement of the digital communication system is possible. One way to do this is to increase in the signalto noise ratio (SNR) by increasing the transmission power or by changing the antenna gain [4], but usually the transceivers with high transmit power are expensive, without mention the transmit permits (depending of the country) required to do so. Also, the physical size restrictions of the nanosatellites and balloon probes makes unfeasible the increase of the power source [5]. The other method is the implementation of a Forward Error Correction (FEC), that is a type of ECC that does not require handshaking between the source and the destination. It is less costly than these techniques. Introducing channel coding in a communication system introduces the possibility of approaching the maximum transmission rate theoretically possible [4]. The FEC method is favorable because have a lower consumption of bandwidth and a highefficiency error correction. This is the reason FEC is suitable for applications in wireless communication [6]. Hence the ReedSolomon codes are chosen
The proposed solution is to have a RS codec implemented in our communication system. The data is compressed in certain format (depending of the type of file), divided in smaller packages, encoded and transmitted through a RF transceiver. From the other side, the Receiver Control Software gather the packages, decode them and detect any erroneous byte and determine their exact location inside the package in order to intent to correct them.
To test that the algorithm does work, we make two tests:

Burst of errors: By passing the data packages through a Random Number Polynomial Generator. In this test we determine the number of errors inserted.

Random errors: By Adding an Additive White Gaussian Noise (AWGN) array, to the data package. The probability of error is independent from one transmitting byte to the next.
For the moment we are not conducting any further tests concerning to the RF signal or the transceivers.
Where:
Fig 3. Typical ReedSolomon codeword
= = + 2
= 2
=
The RS codes may be shortened by (conceptually) making a number of data symbols zero at the encoder, not transmitting them, and then reinserting them at the decoder.
Fig 1. Flowchart of singlesend mode
Fig 2. Flowchart of the unidirectional receiver function in the Control Software

REEDSOLOMON CODES
The ReedSolomon (RS) codes are a subset of BCH codes (BoseChaudhuriHocquenghem codes), that is a class of cyclic errorcorrecting codes that are constructed using polynomials over a Galois field [8][9][10]. With a wide range of applications in digital communications and storage, ReedSolomon codes are able to detect and correct multiple symbol errors [7].
A ReedSolomon code is specified as (, ) with mbit symbols [14]. This means that the encoder takes "" data symbols of "" bits each and adds parity symbols to make an "" symbol codeword. There are parity symbols of "" bits each (Fig. 3). A ReedSolomon decoder can correct up to symbols that contain errors in a codeword, where 2 = .
In our software, we already know that this zerobytes are not important, so we adapt the calculations so we can ignore these added zerobytes and save computing resources.
We define the package size to encode/decode:
= 128
The proposed the number of bytes of parity and hence the max number of error detection per package :
2 = 32
Number of bytes than can be corrected per package of :
= 16
When a target file is requested to the onboard computer, the data array is divided into small pieces of 128 bytes, then it is encoded and concatenated with its respective parity bytes and then send. For the purpose of this paper, we are only going to describe briefly the mathematic procedure followed to implement the RS codes without taking into details.

FINITE (GALOIS) FIELD
ReedSolomon codes are based on a specialist area of mathematics known as Galoisfields algebra. A Galoisfield or finitefield is a set of elements in which we can do addition, subtraction, multiplication, and division without leaving the set. The operation of addition and multiplication must satisfy the commutative, associative, and distributive laws. The number of elements in a field is called the order of the field and, according to Galois, in order for a filed to be finite, the numbers of elements are where is a prime number and is a positive integer (Eq. 1).
( ) = {0,1, . , 1} (1) As we are dealing with information represented in binary, we are going to focus in the binary field (2) and the extension field (2) (Eq. 2 and 3), where addition is EXCLUSIVE OR (XOR) and multiplication is AND. Since
= 5 + 4 + 3
+
= 5 + 3 +2
+ 1
= ()
=
10
= 10 ()
= 6 + 5 + 4
+ 2
19
= 19 ()
= 6 + 4 + 3
+
2
= 2 ()
= 2
11
= 11 ()
= 7 + 6 + 5
+ 3
20
= 20 ()
= 7 + 5 + 4
+ 2
3
= 3 ()
= 3
12
= 12 ()
= 7 + 6 + 3
+ 2 + 1
21
= 21 ()
= 6 + 5 + 4
+ 2 + 1
4
= 4 ()
= 4
13
= 13 ()
= 7 + 2 +
+ 1
22
= 22 ()
= 7 + 6 + 5
+ 3 +
5
= 5 ()
= 5
14
= 14 ()
= 4 + + 1
23
= 23 ()
= 7 + 6 + 3
+ 1
6
= 6 ()
= 6
15
= 15 ()
= 5 + 2 +
24
= 24 ()
= 7 + 3 + 2
+ + 1
7
= 7 ()
= 7
16
= 16 ()
= 6 + 3 + 2
25
= 25 ()
= + 1
= 5 + 4 + 3
+
= 5 + 3 + 2
+ 1
= ()
=
10
= 10 ()
= 6 + 5 + 4
+ 2
19
= 19 ()
= 6 + 4 + 3
+
2
= 2 ()
= 2
11
= 11 ()
= 7 + 6 + 5
+ 3
20
= 20 ()
= 7 + 5 + 4
+ 2
3
= 3 ()
= 3
12
= 12 ()
= 7 + 6 + 3
+ 2 + 1
21
= 21 ()
= 6 + 5 + 4
+ 2 + 1
4
= 4 ()
= 4
13
= 13 ()
= 7 + 2 +
+ 1
22
= 22 ()
= 7 + 6 + 5
+ 3 +
5
= 5 ()
= 5
14
= 14 ()
= 4 + + 1
23
= 23 ()
= 7 + 6 + 3
+ 1
6
= 6 ()
= 6
15
= 15 ()
= 5 + 2 +
24
= 24 ()
= 7 + 3 + 2
+ + 1
7
= 7 ()
= 7
16
= 16 ()
= 6 + 3 + 2
25
= 25 ()
= + 1
the only invertible element is 1, division is the identity function.
(2) = {0, 1} (2)
(2 ) = {0,1, , 2, 3, , 22} (3)
The elements in the extended (2) are mbit symbols. Since we are dealing with arrays of bytes, hence:
(28) = (256) = {0,1, , 2, , 254} (4)

PRIMITIVE POLYNOMIAL AND FIELD
SYMBOLS
Polynomials over the binary field (2) are any polynomials with binary coefficients. Each of these polynomials, denoted as (), is simply the product of its irreducible factors. An irreducible polynomial () of degree is said to be primitive () if the smallest positive integer for which () divides + 1 is = 2 1 The primitive polynomials are polynomials that generate the elements contained in a finite field which in turn are needed to define the RS Codes.
The primitive polynomial determined for a (28) are shown in the table 1:
TABLE 1. PRIMITIVE POLYNOMIALS OF GF (256)
8 + 4 + 3 + 2 + 1
8 + 5 + 3 + + 1
8 + 5 + 3 + 2 + 1
8 + 6 + 3 + 2 + 1
8 + 6 + 4 + 3 + 2 + + 1
8 + 6 + 5 + + 1
8 + 6 + 5 + 2 + 1
8 + 6 + 5 + 3 + 1
8 + 6 + 5 + 4 + 1
8 + 7 + 2 + + 1
8 + 7 + 3 + 2 + 1
8 + 7 + 5 + 3 + 1
8 + 7 + 6 + + 1
8 + 7 + 6 + 3 + 2 + + 1
8 + 7 + 6 + 5 + 2 + + 1
8 + 7 + 6 + 5 + 4 + 2 + 1
8 + 4 + 3 + 2 + 1
8 + 5 + 3 + + 1
8 + 5 + 3 + 2 + 1
8 + 6 + 3 + 2 + 1
8 + 6 + 4 + 3 + 2 + + 1
8 + 6 + 5 + + 1
8 + 6 + 5 + 2 + 1
8 + 6 + 5 + 3 + 1
8 + 6 + 5 + 4 + 1
8 + 7 + 2 + + 1
8 + 7 + 3 + 2 + 1
8 + 7 + 5 + 3 + 1
8 + 7 + 6 + + 1
8 + 7 + 6 + 3 + 2 + + 1
8 + 7 + 6 + 5 + 2 + + 1
8 + 7 + 6 + 5 + 4 + 2 + 1

GENERATOR POLYNOMIAL


A RS codeword is generated using this polynomial, it is defined by the size of the paritybytes and composed of the minimal polynomial of the (2). It is used for the encoding and decoding the message [12].
Once the size of the paritybytes (2) is chosen, that is powers of (2), it is proceeded to compute all their minimal polynomials in order to produce the generator polynomial. For each consecutive power of , the minimal polynomial will be and the generator polynomial is constructed using the next expression:
+ 21
The equation 5 is the primitive polynomial used in our algorithm:
() = ( )
=
(7)
() = 8 + 4 + 3 + 2 + 1 (5)
The field symbols or primitive elements that conform
(2) are determined using the modulo method (Eq. 6)
= () () (6)
Where is the power of the first consecutive root in
(). The proposed value 2 = 32 and the first consecutive root = 0, therefore:
31
0 = 0 () = 0 
8 = 8 () = 4 + 3 + 2 + 1 
17 = 17 () = 7 + 4 + 3 
1 = 1 () = 1 
9 = 9 () 
18 = 18 () 
0 = 0 () = 0 
8 = 8 () = 4 + 3 + 2 + 1 
17 = 17 () = 7 + 4 + 3 
1 = 1 () = 1 
9 = 9 () 
18 = 18 () 
TABLE 2. SAMPLE OF THE FIRST 27 ELEMENTS OF GF (256)
() = ( )
=0
(8)
() = ( 1)( )(
2)( 3) (
31)
(9)
Using Galois algebra for a binary field we obtain our generator polynomial (Eq. 10):
() = 32 + 1031 + 630 + 10629 + 19028
+ 24927 + 16726 + 425 + 6724 + 20923
+ 13822 + 13821 + 3220 + 24219 + 12318
+ 8917 + 2716 + 12015 + 18514 + 8013
+ 15612 + 3811 + 6910 + 1719 + 608
+ 287 + 2226 + 805 + 524 + 2543 + 1852
+ 220 + 241 (10)
In the fig. 4, it is shown the results of our generator polynomial function in the communication software.
4. Calculate the decoded code word from the received word

SYNDROME CALCULATIONS
Every codeword is created so that it can be divided by the generator polynomial (), therefore, if we evaluate a word in any of the roots of (), we will obtain 0 (no errors) as result only if it is a codeword.
A RS codeword has 2 syndromes that depend only on errors (NOT on the transmitted codeword). We can get the syndromes by evaluating the word in the roots of the generator polynomial () are the roots of the generator.
The ith syndrome is defined as:
= () + () = 0 + ()

Output of our own function in Python
= ( )
=1
(14)
Lets define the error locator as = and the error
values as = , then the syndromes can be written in terms of these error locators and error values as:
=

Output using the rsgenpoly function in MATLAB
Fig 4. Test of our generator polynomial function where we obtain the coefficients

RS ENCODING
Now with the generator polynomial, the paritycheck polynomial can be defined by using the next expression:
=1
1 2
1 2
= 1 + 2 + (15)
The syndromes give a system of 2 equations in
2 unknowns.
2
2
() = ( ()) () (11)
1
1
1
1
1
1
1
2
2
2 2 2
And then we can define the codeword as:
[ ] = [ ] 1 2(16)
() = () + () (12)
2
[2 2 2] 
RS DECODING
We define the received data as () and is the sum of the original codeword () plus the errors/erasures ()
() = () + () (13)
The decoding process takes a quite large process that the R S encoding:

Calculate the syndrome components from the received word

Calculate the errorlocator word from the syndrome components
1 2
If every syndrome is zero, then we can be sure that the codeword has no errors, by the other hand, if just a syndrome is different from zero, the codeword does not have one of the roots, therefore it cannot be divided by (). If that case happens, it is necessary to detect the errors.



ERROR LOCATOR POLYNOMIAL
In order to solve the Eq. 16, it is precise to determine the Errorlocator polynomial (Eq. 17), which has got
11, 11, 1as roots.

Calculate the error values from the syndrome components and the errorlocator numbers
() = (1 )
=1
(17)
() = 1 + 1 + + 11 + (18) (1)+ = 0 (19)
For all the errors (different values of k):
=

PROGRAM TESTING
(25)
The RS codec has been implemented in two programming
languages: Python for the onboard software running in the
+ + 1 +1 + + = 0
miniPC and in C# for a laptop with Windows OS (Fig. 5).
=1
=1
=1
(20)
Substitute the Eq. 15 in Eq. 20 and we get the next linear system
+ + 1+1 + + = 0 (21)
To solve such system, there are several algorithms to do so, the most popular are the BerlekampMassey algorithm [10][11] and the PetersonGorensteinZierler algorithm [15]; and to find the roots (x) of the error locator polynomial it can be used the Chien search algorithm [16].


ERROR CORRECTION
Once the error locations are known, the next step is to try to estimate the original value of . This can be achieved by using the Forney algorithm [11][13].
(1)
Fig 5. Receiver Control Software
The transceiver (Fig. 6) work in the band of 433MHz, with a bandwidth of 1KHz, the modulation is GFSK. The majority of the COTS transceivers have a low bittransfer
=
(22)
(1)
rate (bps) as well as a low size of bufferI/O of no more than a hundred of bytes, so to avoid an overrun of the buffer, it is
The error evaluator polynomial is computed as follow:
() 2+1 = ()() (23)
And polynomial ()
() = 1 (24)
The error values are then used to correct the received values at those locations to recover the original codeword.

PERFORMANCE METRICS OF DIGITAL
COMMUNICATIONS
We can almost say for sure than the main goal of the digital communications systems is the accurate transfer of data bits as fast as possible [19]. The primary measure we are going to use to evaluate the RS performance is the Bit Error Rate or BER.
The BER can be defined as the estimated probability of bit errors, in practical testing, it is measured by transferring a finite number of bits through the system and count the incorrectly received bits by comparing with the original data (Eq. 25) [20].
necessary to send every package and wait an interval of time, depending of the transceiver model, to finish the sending [2][18].
Fig 6. Raspberry Pi with the transceiver
The JPEG format is selected as a target file (Fig. 7) due to the Huffman encoding [2][17], even a single erroneous byte set in the wrong place can compromise the entire file,
Format: JPEG; Size (bytes): 19,421
Error inserted
10 bytes
Before RS decoding
After RS decoding
700 bytes
Before RS decoding
After RS decoding
Format: JPEG; Size (bytes): 19,421
Error inserted
10 bytes
Before RS decoding
After RS decoding
700 bytes
Before RS decoding
After RS decoding
corrupting it. The image is a picture of the Large Millimeter Telescope Alfonso Serrano located at the VolcÃ¡n Sierra Negra.
Fig 7. Original image target for the transmission tests
As mentioned before, during the transmission, the package passes through an error burst generator block (Fig. 8), where a certain random number function generates a burst of errors to be inserted in the data, the quantity of errors is determined by us manually during every test. For the AWGN test, the block generates a whitenoise signal array where we only determine the standard deviation and the mean of the signal noise, so it is expected than the number of errors be above of 2t in some cases, meaning that some images will not be fully recovered.
Fig 8. Flowchart of the Random number generator is placed in the program for testing the RS decoder

EXPERIMENTAL RESULTS
The algorithm has been able to receive the image data, decode every package and concatenate it to restore the original file as it is shown in the table 3. As a comparison, it is also shown the image file as it would be before the RS decoding.
TABLE 3. IMAGE FILE RECEIVED THROUGH RADIO DURING THE BURST ERROR TEST.
The AWGN test results are shown in the table 4 and 5, where it is observed than, since we cannot set the quantity of errors to be below 2t, the file is partially recovered but legible.
To measure the performance of the data transmission, we calculate the BER before and then after the RS decoding. This is achieved by comparing the original data sent, before adding the AWGN, with the data decoded in the Receiver Control Program (Table 4). This process was done several times using different image data sizes.
No. test
Total bits
Total error bits
Error bits unable to correct
BER
before RS decoding
BER after RS
decoding
1
32,552
1,080
40
3.3
Ã— 102
1.2 Ã— 103
2
63,000
2,280
35
3.6
Ã— 102
5.6 Ã— 104
3
83,568
3,082
47
3.7
Ã— 102
5.6 Ã— 104
4
155,368
6,215
105
4 Ã— 102
6.8 Ã— 104
No. test
Total bits
Total error bits
Error bits unable to correct
BER
before RS decoding
BER after RS
decoding
1
32,552
1,080
40
3.3
Ã— 102
1.2 Ã— 103
2
63,000
2,280
35
3.6
Ã— 102
5.6 Ã— 104
3
83,568
3,082
47
3.7
Ã— 102
5.6 Ã— 104
4
155,368
6,215
105
4 Ã— 102
6.8 Ã— 104
TABLE 4. BER CALCULATIONS USING THE DATA RECEIVED AND DECODED
After RS decoding
As we can observe in the table 4, the BER value decreased, meaning an improvement in the transmission. For example, in the test No. 4, the BER before the RS decoding is
2
4 Ã— 10 , that is for every 100 bits, there are 4 erroneous
TABLE 5. IMAGE FILE RECEIVED DURING THE AWGN TEST
Format: JPEG; Size (bytes): 19,421
Before RS decoding
bits. After the RS decoding the BER goes down to
6.8 Ã— 104, meaning that for every 10,000 bits, there is just around 7 erroneous bits.

CONCLUSIONS

We have been able to implement a working RS codec that can be used in ARMbased OBC as well as ported to Windows OS. We testes their performance using entirely lowcost COTS transceivers and determined that it is capable to find and correct errors in data files of different sizes. To improve the performance of the RS codec, it is required further analysis of the time execution.
REFERENCES

Lovascio, A., DOrazio, A. and Centonze, V., 2020. Characterization of a COTSBased RF Receiver for Cubesat Applications. Sensors, 20(3), p.776.

ValadezCampos, E., MendozaTorres, E. and DeRoaCampoy, A., 2021. Lowcost testing platform for highaltitude balloon flights. Educative Clues (Pistas Educativas), 42(136), p.21. Available at:
<http://www.itcelaya.edu.mx/ojs/index.php/pistas/article/view/2425/ 0> [Accessed 16 February 2021].

Langer, Martin & Bouwmeester, Jasper., 2016. Reliability of CubeSats Statistical Data, Developers' Beliefs and the Way Forward. Proceedings of the AIAA/USU Conference on Small Satellites, SSC16X2.

Sklar, B. and Harris, F., 2004. The ABCs of linear block codes. IEEE Signal Processing Magazine, 21(4), pp.1435.

De Milliano, M. and Verhoeven, C., 2010. Towards the next generation of nanosatellite communication systems. Astronautic Act (Acta Astronautica), 66(910), pp.14251433.

Phat Nguyen Huu and Vinh TranQuang, Takumi Miyoshi., 2012. Multihop ReedSolomon encoding scheme for image transmission on wireless sensor networks. Fourth International Conference on Communications and Electronics (ICCE).

Sanjana P. Choudhari, Megha B. Chakole., 2017, Reed Solomon code for WiMAX network, 2017 International Conference on Communication and Signal Processing (ICCSP), pp. 176179.

N. Ambramson., Information Theory and Coding, 1963, McGraw Hill, USA.

E.R. Berlekamp Algebraic Coding Theory, 1968, McGrawHill, New York (USA).

R.T. Moenck. Practical fast polynomial multiplication. In Proc. 3rd ACM Symposium on Symbolic and algebraic computation, pages 136148. ACM, 1976.

Blahut R. E., 2003, Algebraic Codes for Data Transmission, Cambridge University Press.

Hamming, R., 1986. Coding and information theory. Englewood Cliffs, N.J.: PrenticeHall.

Forney, G., 1965. On decoding BCH codes. IEEE Transactions on Information Theory, 11(4), pp.549557.

Tilavat, V., & Shukla, Y. (2014). Simplification of procedure for decoding ReedSolomon codes using various algorithms: an introductory survey. International Journal of Engineering Development and Research, 2(1), 279283.

Peterson, W., 1960. Encoding and errorcorrection procedures for the BoseChaudhuri codes. IEEE Transactions on Information Theory, 6(4), pp.459470.

Chien, R., 1964. Cyclic decoding procedures for Bose Chaudhuri Hocquenghem codes. IEEE Transactions on Information Theory, 10(4), pp.357363.

H. T. Sencar and N. Memon, 2009. Identification and recovery of JPEG files with missing fragments, Digital Investigation, vol. 6, pp.
S88S98

Freebsd.org. 2020. Serial and UART Tutorial. [online] Available at:
<https://www.freebsd.org/doc/en_US.ISO88591/articles/serial uart/index.html> [Accessed 18 February 2021].

Mitic, D., Lebl, A. and Markov, Z., 2012. Calculating the required number of bits in the function of confidence level and error probability estimation. Serbian Journal of Electrical Engineering, 9(3), pp.361 375.

Sklar, B., 2001. Digital communications. Upper Saddle River, N.J.: Prentice Hall PTR.