N
N
NikSIk312019-11-02 01:40:51
Algorithms
NikSIk31, 2019-11-02 01:40:51

Reed Solomon Code Algorithm?

Good day.
I want to implement Reed Solomon's codes. Having looked that there are no tutorials anywhere on how to programmatically do this, you have to do it yourself. There are some long implementations on the github and it’s hard to figure them out (especially when a complex algorithm that requires a certain base is described by a person with stronger knowledge of the language). Therefore, you have to do it yourself.
I analyzed the algorithm and want to know how close I am to the truth and at the same time I would like to fill in the gaps along the way. So, let's start:
1) There is an input message (for example, we declare a string of two words "Hello world!")
2) Then it’s hard for me to say exactly how this string is converted (should it be converted to binary code or what?) I just looked at the example on numbers (there was a vector of numbers) this vector of numbers was multiplied by the generating matrix
About the matrix: it consists of two pieces
# the first is an identity matrix (the length of a vector of words)
# the second is some numbers (as I understand it, they must be defined in order to be able to multiply, divide, and all this was done well in the computer concept) - for example, we build two tables "multiplication " and "addition" are all modulo fields. And what to do next with them? And what field size to take?
3) After that, you need to multiply this matrix by a vector of elements of the input message and get a vector with a message + redundant numbers, in fact, this is encoding.
----
4) Modify this vector a little to create "supposedly noise"
----
5) To decode, take the modified vector and multiply by the inverse matrix (to the generator matrix, then without rows in which we modeled "noise") and the result will be the original message.
Damn, that's all I understood. Honestly tried, but it turned out so-so. Of the main points that are not clear to me in the implementation:
1) How to make a vector of strings, more precisely, what to do if there is a string? Those. Again, on numbers, a vector of numbers seems to be understandable, and multiplying such a vector by a matrix is ​​understandable.
2) Generative matrix, how to generate these numbers in it, which come after the identity matrix? It seems that there is something connected with the Galois field
2.1) If you still need a Galois field, then what is its size?
Wow, well, then I don’t know, probably you shouldn’t ask about matrix multiplication and finding the inverse .. (I can do it with ordinary numbers, I hope it will be the same here, without surprises)
As you understand, I’m not strong in this topic, I honestly tried to understand. I looked at Habré, looked at YouTube, but something is a bit complicated in some places. If there was a ready-made implementation, it would be great, otherwise on the github I look at some libs with fancy code and implementation, which are difficult for me to understand.
I hope for your understanding

Answer the question

In order to leave comments, you need to log in

Didn't find what you were looking for?

Ask your question

Ask a Question

731 491 924 answers to any question