0
$\begingroup$

I'm creating a RS(15,9) code and can't figure out how to determine when T>t (T>3) by using the syndrome components. I understand that to determine the error count you use the largest TxT matrix whose determinant is NOT equal to zero. However, by this logic, the only way to determine if T>3 would be to calculate the determinant of a 15x15 matrix, then 14x14, then 13x13, etc. Is there any better way to do this?

When I run my current code with a certain set of 4 errors, it triggers the T=2 errors condition, and actually attempts to correct errors in the wrong position (making the decoded message even more incorrect).

Here is my current Verilog code used to determine error count. Thank you in advance for any help

  det[0] = multiply(syndromeComponent[2],syndromeComponent[4]) ^ multiply(syndromeComponent[3],syndromeComponent[3]); // Represents det3,4
  det[1] = multiply(syndromeComponent[1],syndromeComponent[4]) ^ multiply(syndromeComponent[3],syndromeComponent[2]); // Represents det2,4
  det[2] = multiply(syndromeComponent[1],syndromeComponent[3]) ^ multiply(syndromeComponent[2],syndromeComponent[2]); // Represents det2,3
  det[3] = multiply(syndromeComponent[0],det[0]) ^ multiply(syndromeComponent[1],det[1]) ^ multiply(syndromeComponent[2],det[2]); //Represents det1,2,3

if((syndromeComponent[0] || syndromeComponent[1] || syndromeComponent[2] || syndromeComponent[3] || syndromeComponent[4] || syndromeComponent[5]) == 0) begin
    T = 0;
  end

  else begin
    i = 0;
    while(i == 0) begin
      if(det[3] != 0) begin
        T = 3;
        i = 1;
      end
      else if(det[0] != 0) begin
        T = 2;
        i = 1;
      end
      else if((divide(syndromeComponent[1],syndromeComponent[0])==divide(syndromeComponent[2],syndromeComponent[1])) && (divide(syndromeComponent[2],syndromeComponent[1])==divide(syndromeComponent[3],syndromeComponent[2])) && (divide(syndromeComponent[3],syndromeComponent[2])==divide(syndromeComponent[4],syndromeComponent[3])) && (divide(syndromeComponent[4],syndromeComponent[3])==divide(syndromeComponent[5],syndromeComponent[4])) && (divide(syndromeComponent[5],syndromeComponent[4])==divide(syndromeComponent[1],syndromeComponent[0]))) begin
        T = 1;
        i = 1;
      end
      end
    end
  end
```
$\endgroup$

1 Answer 1

1
$\begingroup$

You don't need to look at inverting $15\times 15$ matrices, only $3\times 3$ matrices, if you are using what is called a Peterson-Gorenstein-Zierler decoder (reasonable for correcting 2 or 3 errors but inefficient when the error-correcting capability is higher). But, in any case, it is necessary to continue the error-correction process to the bitter end to determine whether the number of errors that the decoder initially thought had occurred (largest $e \leq t$ such that a specific $e\times e$ determinant is nonzero), and the actual number of errors that the later parts of the error-correction process corrected. Sometimes, the error-locator polynomial has degree $e^\prime \leq t$ but it has fewer than $e^\prime$ roots in the field (as revealed by the Chien search), which is an indication that something is awry. This is called decoder failure and decoders ought to output a separate signal to the recipient that the symbols that just came out of the data output of the decoder (hardware implementations) or are about to be sent out (software implementations) are unreliable and definitely contain errors. Whether a decoder implementation sends such a signal (and whether the recipient uses this information in any way), are matters beyond the scope of this question.

Read this answer of mine, which, although it talks about Berlekamp-Massey and Extended Euclidean Algorithm (EEA) decoders and not about PGZ decoders, has much useful information. If you wish to blow your mind further, read the papers: D. V. Sarwate and R. D. Morrison, "Decoder Malfunction in BCH Decoders," IEEE Transactions on Information Theory, pp. 894-899, July 1990, and M. Srinivasan and D. V. Sarwate, "Malfunction in Peterson-Gorenstein-Zierler Decoders" IEEE Transactions on Information Theory, pp. 1649-1653, September 1994 which show that it is possible for a PGZ decoder or a EEA decoder to sometimes find an error-locator polynomial of degree $e^\prime \leq t$ and to "correct" $e^\prime$ errors (error-locator polynomial has $e^\prime$ roots in the field) and so think that everything is hunky-dory and there is no need to send a decoder failure signal, but in fact, the decoder output is not a valid codeword at all; the error-correction process actually has introduced more errors rather than correct the errors that were already there.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.