-1

I am studying cyclic codes. From what I understood of it, a cyclic code is a special kind of linear code with the property that any codeword cyclic shift is also a codeword.

Generally, we start with number of message bits $k$ and number of code bits $n$ in a codeword and then try to build a cyclic code with these requirements. I am thinking of writing a GF(2) cyclic code in the following way and want to know the problems with this approach:

I take a codeword of size $n$ such that circular shifts of it (max possible $n-1$) gives $k$ linearly independent vectors. I take all linear combinations and circular shifts of these linear combinations of these codewords and include them in code. It has dimension $k$ and $n$ code bits.

Are there any theorems about circular shifts of the linear combinations? Since we have taken all the circular shifts of the original codeword, is it sufficient if we take all the linear combinations OR we should also specifically add the circular shifts of these linear combinations so as to NOT violate the cyclic property of a cyclic code?

MBaz
  • 15,314
  • 9
  • 30
  • 44
Seetha Rama Raju Sanapala
  • 649
  • 1
  • 7
  • 17
  • better ask this question at data-coding, information theory or communication forums. – Fat32 Mar 16 '16 at 10:57
  • @Fat32 Questions about channel coding and (not too mathematical) info theory have generally been on-topic here (and I hope they continue to be). – MBaz Mar 16 '16 at 13:55
  • @Fat32:Why are channel coding and data-communications tags available here then? To my experience, this site has one of the most knowledgeable persons. Negative comments and votes should be moderated. – Seetha Rama Raju Sanapala Mar 16 '16 at 13:59
  • @Mbaz, if it is so, those tags shold be removed, since digital signal processing has little if nothing to do with data coding and information theory whose domain is probability & algebra and whose target is data storage and communications. Of course there are DSP people who can also answer coding questions, just as they could answer sensor electronics questions. But then it would be hard to maintain the boundary. Nevertheless that's my point of view. There is no harm in a correct answer :) – Fat32 Mar 16 '16 at 14:25
  • Channel coding and data communications are very much part of DSP as can be seen in any M.Tech programs in SP. – Seetha Rama Raju Sanapala Mar 16 '16 at 15:08
  • @SeethaRamaRaju yes they are higly involved. – Fat32 Mar 16 '16 at 15:17
  • Since you refuse to consider the polynomials-as-codewords approach to cyclic codes (cf. this question), you have a difficult job ahead. In a journey of a thousand (or is it 1024?) steps, the first one

    I take a codeword of size $n$ such that circular shifts of it (max possible $n−1$) gives $k$ linearly independent vectors.

    is the hardest.

     – Dilip Sarwate Mar 16 '16 at 21:28
  • @Dilip Sarwate:To fully understand the impact of polynomials approach, one should experience the difficulties in the other method. That is what I am trying to realize the hardships in my method. The step you mentioned is the easiest I think. (I may be completely wrong.). Suppose I want n=5 and k=3, I take 10000, 01000, 00100 as the vectors. To be cyclic, I have to take the circular shifts of each of these and linear combinations of these. So at least 8 codewords are there in this code. And can be more because you are including the shifts of them also. So I face some other issues now. – Seetha Rama Raju Sanapala Mar 17 '16 at 01:01

1 Answers1

0

A few comments:

  • It's not evident to me that your algorithm will produce $2^k$ codewords that are linear and cyclic. Have you tried it out?
  • It's not evident how you're going to assign codewords to inputs. This may seem trivial for small codes but becomes harder and harder as the code grows.
  • It's not evident how you're going to calculate the code's minimum distance. Again, this is easy to do by brute force for small codes, but impossible for large codes.
  • And the most important question: how are you going to decode this code?

See also related questions such as: Generate Minimum distance codes

MBaz
  • 15,314
  • 9
  • 30
  • 44
  • Very useful comments @MBaz. I also thought there should be some problem(s) with this approach and wanted to know. For second comment I am thinking like this - for simplicity let us choose k =3. Then I assign 3 linearly independent codewords ( could be shfits of one code word) to 001, 010 and 001 inputs. Then I can form codewords for all the 8 possible messages with the linear combinations of the 3 original codewords. Does this approach have a problem - ignoring Hamming code for a moment? – Seetha Rama Raju Sanapala Mar 16 '16 at 06:48
  • Of course, I should get 8 different codewords through these linear combinations. Otherwise, I will have a problem. In this context only, I was asking whether there are any theorems which guarantee these things. I think in the text books, we find a lot of theorems without explaining explicitly why these are important to channel coding. – Seetha Rama Raju Sanapala Mar 16 '16 at 06:50
  • @SeethaRamaRaju Give me an example with, say, $n=5$. Remember that a linear code must include the all-zero codeword. – MBaz Mar 16 '16 at 13:51
  • @SeethaRamaRaju By the way, I agree about the textbooks (most of them, anyway). Have you seen this book: http://www.inference.phy.cam.ac.uk/mackay/itila/ ? I cannot recommend it highly enough. – MBaz Mar 16 '16 at 13:52
  • :all-zero codeword is a codeword always because it is one of the linear combinations:all vectors multiplied by zero and summed. I will think about your other question n=5 and respond. Your points are very helpful. – Seetha Rama Raju Sanapala Mar 16 '16 at 14:05