I have an array of N bits written on a cyclic tape. I read a sequence of M symbols starting from a random place on the tape. I was thinking about Reed Solomon error correction trying all possible starting points of the message, but all RS implementations work with bytes, at least. Is this an implementation issue or RS requires a certain power in Galois field and cannot work with smaller sizes?
I've also tried to experiment with LDPC and Hamming codes, but they restore all the messages, so there is not built-in sanity check which I could use for detection of the starting point of the message.
In the case of GF(2), use BCH error correcting code where the data and parities are single bits, but the error correction process generates syndromes which are elements of GF(2^n), where n is chosen based on how many bits are to be corrected and message size (including the parity bits).
https://en.wikipedia.org/wiki/BCH_code
The wiki BCH code article doesn't mention that Berlekamp Massey or Sugyama extended Euclid methods can also be used to convert syndromes into an error locator polynomial. These are explained in the RS article. Since symbols are single bits, error values are always == 1 and do not need to be calculated:
https://en.wikipedia.org/wiki/Reed%E2%80%93Solomon_error_correction#BCH_view_decoders
RS error correction code operates within a finite field of GF(p^n), where p is any prime number and n >= 1, with p^n possible symbols, and maximum message length including parity symbols is p^n-1 for typical "BCH view" RS implementations. or p^n for the less popular "original view" implementations.
https://en.wikipedia.org/wiki/Reed%E2%80%93Solomon_error_correction#Constructions
You can use smaller fields for RS code, such as GF(2^3) (3 bit symbols), with maximum message size for "BCH view" RS of 7 symbols including parities. Using GF(2^4) increases this to 15 symbols, GF(2^5) to 31 symbols, ...