Open abhishekmittal15 opened 1 year ago
Attention: Patch coverage is 23.07692%
with 90 lines
in your changes missing coverage. Please review.
Project coverage is 94.89%. Comparing base (
a140a46
) to head (34914af
). Report is 82 commits behind head on release/0.3.x.
Files | Patch % | Lines |
---|---|---|
src/galois/_codes/_hamming.py | 21.73% | 90 Missing :warning: |
:umbrella: View full report in Codecov by Sentry.
:loudspeaker: Have feedback on the report? Share it here.
Hi @mhostetter , I wanted to share my current thoughts on implementing it for prime fields GF(q)
and get your feedback
Parity check matrix generation
Loop over numbers from $1$ to $q^r - 1$
a
( $1 \le a \le q-1$) and then get its integer representationa
from $1$ to $q-1$, after dividing it by a
, the integer representation is not lesser than the current number, then it is fine to add the number representation(in vector form) to the parity check matrix, else it is not, as this is just a scaled representation of a column already added earlier.To get the number representation I am thinking of using the integer_to_poly
method in galois\_polys\_conversions.py
to get the number representation in the field GF(q)
and also use the poly_to_integer
to get the base10 number. I think this
approach should work, but my concern is that it will look absurd to be calling a polynomial related function in the hamming class. How do you suggest I go about this?
Error Detection Detection is the same in any number of errors ⇒ return 1 if syndrome is non zero.
Error Correction If $c = v+e$ is our corrupted codeword where $v$ is an arbitrary codeword and $e$ is a weight $1$ vector. This is a single error, and after multiplying to parity check we get $He$. Due to $e$ being a weight $1$ vector, the syndrome is just one of the scaled column of the parity check matrix. So for this I am thinking of just looping over all the parity columns and then checking if its a scaled vector of the syndrome or not. This remains the same irrespective of the number of errors since we only attempt to correct $1$ error.
Parity Check Matrix Generation Will do the same as above, but now just add $0's$ column and a $1's$ row.
Error Detection Since I can detect $0, 1, 2$ errors now. To check if there is only $1$ error, I would have to go through all the parity columns and check if the syndrome is a scaled parity column or not. If it is, then I know its 1, else I just return 2.
Error Correction We now first detect the number of errors, and only try to correct it if the number of errors is 1(if its 2 just ignore it, as it cant be corrected).
Let me know your suggestions.
To get the number representation I am thinking of using the integer_to_poly method in galois_polys_conversions.py to get the number representation in the field GF(q) and also use the poly_to_integer to get the base10 number. I think this approach should work, but my concern is that it will look absurd to be calling a polynomial related function in the hamming class. How do you suggest I go about this?
I can't vouch for the algorithm. But here's some thoughts on doing what you describe.
In [1]: import numpy as np
In [2]: import galois
In [3]: q, r = 5, 3
In [4]: GF = galois.GF(q**r)
# Lists all numbers 0 to q^r - 1. You can loop through this array if you'd like
In [5]: GF.elements
Out[5]:
GF([ 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13,
14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27,
28, 29, 30, 31, 32, 33, 34, 35, 36, 37, 38, 39, 40, 41,
42, 43, 44, 45, 46, 47, 48, 49, 50, 51, 52, 53, 54, 55,
56, 57, 58, 59, 60, 61, 62, 63, 64, 65, 66, 67, 68, 69,
70, 71, 72, 73, 74, 75, 76, 77, 78, 79, 80, 81, 82, 83,
84, 85, 86, 87, 88, 89, 90, 91, 92, 93, 94, 95, 96, 97,
98, 99, 100, 101, 102, 103, 104, 105, 106, 107, 108, 109, 110, 111,
112, 113, 114, 115, 116, 117, 118, 119, 120, 121, 122, 123, 124],
order=5^3)
# You can take an integer representation of a field element in GF(q^r) and represent it as a r length vector over GF(q)
# This is equivalent to integer_to_poly()
In [6]: GF(85).vector()
Out[6]: GF([3, 2, 0], order=5)
# Or you can go the other way
# This is equivalent to poly_to_integer()
In [7]: GF.Vector([3, 2, 0])
Out[7]: GF(85, order=5^3)
Hi, yea thats perfect for what I require.
Thanks
Hi @mhostetter , I have extended the Hamming class to support prime fields now.
I have made a demo of its working here
One catch is that the generator matrix is always systematic, not sure if somebody would want it to be non systematic...
Also I was wondering if the detect
function could return the actual number of errors, rather than just a boolean value. Or maybe we could create another function that does this?
Let me know what you think about it
Hi @mhostetter,
Wanted to know if you got a chance to look at the current working demo linked in the previous comment?
@abhishekmittal15 sorry for the delayed response. I did just look at your example notebook. It looks good to me. The API seems consistent with the APIs for the other FEC codes.
Glad to hear that @mhostetter . I have been thinking of supporting haaming codes for extension fields too, but since I am a bit rusty in remembering its theory, I have been giving it a read from my notes and the galois docs. Meanwhile i think i will add the necessary docstrings to the functions, to update the docs.
I'm sorry! I deleted release/0.3.x
and this automatically closed. I reinstated that branch and will re-open.
Hi, I have written a working version of hamming codes in GF(2). I will soon clean up the functions a little more and add docstrings.
Then we can discuss on implementing extended Hamming codes.
Please let me know, if you have any feedback
Thanks!!