1
$\begingroup$

Given that

  • The channel is tiny, it has message size of 72 bits
  • Each bit is probabilistic, meaning that I have a value between 0 and 100 of how likely that bit is on/off1
  • Only 24 bits of acutal data are needed

Currently, BCH[63,24,7] is the closest thing I've found, but it doesn't capitalize on all aspects of the channel. It isn't probabilistic and 9 of the 72 bits are unused.

Can anyone suggest an algorithm that can perform better on this type of channel?

1 The bits are derived from pixels on a greyscale image (values 0 to 255) read from a camera by the recipient of the code. Any pixel P ≤ 128 translates to 0, otherwise 1. Due to the lighting conditions when the image is taken, some bits are more likely to be erroneous. For example, half of the image is in a shadow, white pixels begin to look more grey, so instead of reading 255 (full white) they read 110 (which is ≤ 128, therefore the bit is 0). So, pixels that are far away from 0 and 255 are more likely to be erroneous, so to speak. The value of each bit is independent. In the end, the algorithm should be able to verify that the bits converted from pixels match a valid codeword and correct them otherwise.

$\endgroup$
  • $\begingroup$ @D.W. When I say probabilistic, I mean that certain bits are more likely to be 1 than 0. (I'm reading from an image, 0-255, anything below 128 is considered 1, and above considered 0, but a value of 120 could go either way.) So, what I'm getting at is that there is more information in each bit than just 1 or 0. Yes, it need to be pretty efficient, so I don't think I could do a random code unless I was able to load it into a hash map or similar. $\endgroup$ – MrZander Oct 17 '17 at 7:35
  • $\begingroup$ @D.W. You're a good mod. I have updated the question, hopefully it answers your question. Maybe probabilistic isn't exactly the correct word to use here. $\endgroup$ – MrZander Oct 18 '17 at 23:37
  • $\begingroup$ Thanks, that helps. So do you want an encoding, where a k-bit message is mapped to a 72-bit codeword, which will then undergo some error process, and finally the recipient will receive the probability that each bit is correct? What is the process? Does each bit go through an independent and identical process? Anyway, it sounds like you want a soft-decision decoder (soft decoding). $\endgroup$ – D.W. Oct 19 '17 at 5:19
  • $\begingroup$ @D.W. Yes, that is essentially what I am after. The recipient is the camera in this case. They will translate the pixel values into bits and check to ensure that the bits form a valid codeword. The bits are independent of one another. $\endgroup$ – MrZander Oct 19 '17 at 5:30
  • 1
    $\begingroup$ I'm not sure what you mean by a "code" not being probabilistic. It's the decoding procedure that you use which cannot handle this information. Perhaps there's another decoding procedure which could. $\endgroup$ – Yuval Filmus Oct 19 '17 at 6:47

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.