Implementation of Reed-Solomon Codes for Stratospheric Balloon Probes and Nano-Satellites

Implementation of Reed-Solomon Codes for Stratospheric Balloon Probes and Nano-Satellites

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 built-in 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 nano-satellites using entirely low-cost commercial components, we develop a communication system to transmit/receive data files above 5KB with low-cost commercial RF transceivers, commercial ARM-based mini-PC and using an implementation of Reed-Solomon codes.

Keywords Tx; Rx; Reed-Solomon Codes; Error Correcting Codes; Components-Off-The-Shelf; ARM-based; Galois field; codec.

1. INTRODUCTION

The use of Components-Off-The-Shelf or COTS based solutions has allowed to develop radio-probes, payloads and mini-satellites 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 signal-to- 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 nano-satellites 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 high-efficiency error correction. This is the reason FEC is suitable for applications in wireless communication [6]. Hence the Reed-Solomon codes are chosen

The proposed solution is to have a R-S 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:

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

2. 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 Reed-Solomon codeword

   = = + 2

   = 2

   =

   The R-S codes may be shortened by (conceptually) making a number of data symbols zero at the encoder, not transmitting them, and then re-inserting them at the decoder.

   Fig 1. Flowchart of single-send mode

   Fig 2. Flowchart of the uni-directional receiver function in the Control Software

   1. REEDSOLOMON CODES

      The Reed-Solomon (R-S) codes are a subset of BCH codes (Bose-Chaudhuri-Hocquenghem codes), that is a class of cyclic error-correcting 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 Reed-Solomon code is specified as (, ) with m-bit 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 Reed-Solomon decoder can correct up to symbols that contain errors in a codeword, where 2 = .

      In our software, we already know that this zero-bytes are not important, so we adapt the calculations so we can ignore these added zero-bytes 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 on-board 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 R-S codes without taking into details.

      1. FINITE (GALOIS) FIELD

         Reed-Solomon codes are based on a specialist area of mathematics known as Galois-fields algebra. A Galois-field or finite-field 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 m-bit symbols. Since we are dealing with arrays of bytes, hence:

         (28) = (256) = {0,1, , 2, , 254} (4)

      2. 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 R-S 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

      3. GENERATOR POLYNOMIAL

A R-S codeword is generated using this polynomial, it is defined by the size of the parity-bytes 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 parity-bytes (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

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

1. 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 R-S 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 i-th syndrome is defined as:

   = () + () = 0 + ()

   1. 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:

      =

   2. Output using the rsgenpoly function in MATLAB

      Fig 4. Test of our generator polynomial function where we obtain the coefficients

      1. R-S ENCODING

         Now with the generator polynomial, the parity-check 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]

      2. R-S 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:

      1. Calculate the syndrome components from the received word

      2. Calculate the error-locator 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.

2. ERROR LOCATOR POLYNOMIAL

   In order to solve the Eq. 16, it is precise to determine the Error-locator polynomial (Eq. 17), which has got

   11, 11, 1as roots.

   1. Calculate the error values from the syndrome components and the error-locator numbers

      () = (1 )

      =1

      (17)

      () = 1 + 1 + + 11 + (18) (1)+ = 0 (19)

      For all the errors (different values of k):

      =

   2. PROGRAM TESTING

      (25)

      The R-S codec has been implemented in two programming

      languages: Python for the on-board software running in the

      + + 1 +1 + + = 0

      mini-PC 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 Berlekamp-Massey 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].

3. 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 bit-transfer

=

(22)

(1)

rate (bps) as well as a low size of buffer-I/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.

1. 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 R-S 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 R-S decoding
   	After R-S decoding
   700 bytes	Before R-S decoding
   	After R-S decoding

   Format: JPEG; Size (bytes): 19,421
   Error inserted
   10 bytes	Before R-S decoding
   	After R-S decoding
   700 bytes	Before R-S decoding
   	After R-S 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 white-noise 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 R-S decoder

   1. 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 R-S 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 R-S 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 R-S decoding	BER after R-S 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 R-S decoding	BER after R-S 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 R-S 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 R-S 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 R-S decoding

      bits. After the R-S decoding the BER goes down to

      6.8 × 104, meaning that for every 10,000 bits, there is just around 7 erroneous bits.

   2. CONCLUSIONS

We have been able to implement a working R-S codec that can be used in ARM-based OBC as well as ported to Windows OS. We testes their performance using entirely low-cost 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 R-S codec, it is required further analysis of the time execution.

REFERENCES

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

2. Valadez-Campos, E., Mendoza-Torres, E. and DeRoa-Campoy, A., 2021. Low-cost testing platform for high-altitude 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].

3. 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, SSC16-X-2.

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

5. De Milliano, M. and Verhoeven, C., 2010. Towards the next generation of nanosatellite communication systems. Astronautic Act (Acta Astronautica), 66(9-10), pp.1425-1433.

6. Phat Nguyen Huu and Vinh Tran-Quang, Takumi Miyoshi., 2012. Multi-hop Reed-Solomon encoding scheme for image transmission on wireless sensor networks. Fourth International Conference on Communications and Electronics (ICCE).

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

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

9. E.R. Berlekamp Algebraic Coding Theory, 1968, McGraw-Hill, New York (USA).

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

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

12. Hamming, R., 1986. Coding and information theory. Englewood Cliffs, N.J.: Prentice-Hall.

13. Forney, G., 1965. On decoding BCH codes. IEEE Transactions on Information Theory, 11(4), pp.549-557.

14. 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), 279-283.

15. Peterson, W., 1960. Encoding and error-correction procedures for the Bose-Chaudhuri codes. IEEE Transactions on Information Theory, 6(4), pp.459-470.

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

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

    S88S98

18. Freebsd.org. 2020. Serial and UART Tutorial. [online] Available at:

    <https://www.freebsd.org/doc/en_US.ISO8859-1/articles/serial- uart/index.html> [Accessed 18 February 2021].

19. 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.

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