2

I am trying to generate a set of linear block codewords of length n and have minimum hamming distance dmin. I understand Hamming codes but they are not flexible with n. One possible way I can think of is brute force search. But when trying to code this in MATLAB I am not sure how to proceed.

Google search helped me find this link where it does exactly what I want. Code Generation Tool

Also I would appreciate any other methods/algorithms which can achieve this in a more efficient way.

PSK
  • 109
  • 7

1 Answers1

1

You don't really put any constraints on the family of codes (not even the alphabet). For real applications, you do need to put more constraints on what you want for a code. And distance may not be so important (e.g. the minimum distance of many LDPC codes is quite low, but you need to decode well beyond distance/2 to come close to capacity on many channels).

Brute force searching a code is a bad idea, since most codes are hard to decode (you need some structure to exploit to decode efficiently). Also, computing the minimum distance is NP hard in general (Vardy, 1997).

Here is an example of a code, which has worked well for many applications (CD's, RAID arrays, TV, Voyager mission, etc.). Reed-Solomon Codes are a family of maximum distance separable (MDS) codes, i.e. for a given length n and number of information symbols k, they have the largest distance possible (n-k+1).

They are also easily decodable, say by the Peterson-Gorenstein-Zierler algorithm or Berklenkamp-Massey algorithm (more efficient). You can apply these to generalized reed solomon codes as well (See R.M. Roth, Introduction to coding theory, for details). Many other codes are related to this family. For example, BCH codes are alternant codes from a RS code.

Batman
  • 1,101
  • 6
  • 12
  • I will look into Reed Solomon codes thanks. But I do not understand why you say distance may not be important. Also what do you mean by "but you need to decode well beyond distance/2 to come close to capacity on many channels" – PSK Aug 13 '15 at 04:10
  • You're guaranteed to be able to theoretically correct all errors up to distance/2 (via the bounded distance decoder). However, for having a high data rate, you need to correct more than distance/2 errors for many error patterns (which is possible, because if you draw a sphere around two codewords larger than distance/2, the overlap is often very small). See chapter 13 (page 212) of Mackay's information theory for more details. Essentially, distance is a worst case property, and a lot of codes which work well (e.g. LDPC) have low distance. – Batman Aug 13 '15 at 12:48
  • Also, I said "may not be so important", not "not be important". The error floors for some codes (e.g. turbo codes) are controlled by low weight codewords. See chapter 48 of Mackay's book for more details. – Batman Aug 13 '15 at 12:54