Dtjytyk

What major Native American tribes were around Santa Fe during the late 1850s?

Have I saved too much for retirement so far?

How to align and center standalone amsmath equations?

Has Darkwing Duck ever met Scrooge McDuck?

What does this horizontal bar at the first measure mean?

Bob has never been a M before

What linear sensor for a keyboard?

My friend sent me a screenshot of a transaction hash, but when I search for it I find divergent data. What happened?

Indicating multiple different modes of speech (fantasy language or telepathy)

Can a significant change in incentives void an employment contract?

Did arcade monitors have same pixel aspect ratio as TV sets?

Does the Mind Blank spell prevent the target from being frightened?

Longest common substring in linear time

Can somebody explain Brexit in a few child-proof sentences?

Open a doc from terminal, but not by its name

How do ground effect vehicles perform turns?

Did US corporations pay demonstrators in the German demonstrations against article 13?

What is the gram­mat­i­cal term for “‑ed” words like these?

Is it possible to have a strip of cold climate in the middle of a planet?

About a little hole in Z'ha'dum

Is there a word to describe the feeling of being transfixed out of horror?

Why is Arduino resetting while driving motors?

How to color a curve

How do I repair my stair bannister?

Syndrome decoding

Decoding and correcting $(1,0,0,1,0,0,1)$ Hamming$ (7,4)$ codeParity check matrix and error syndromesUse a parity check matrix for Ham(4,2) and syndrome decodingWhen decoding a block code, how do you know which error a syndrome corresponds to?Finding error patterns from a syndromeConstructing syndrome decoding tableHow many codewords with same syndrome and weightSyndrome decoding and error correctionSyndrome decoding algorithmsUnderstanding the received vector in syndrome decoding

0

$begingroup$

I have a conceptional question to the concept of "syndrome decoding" (i.e. the procedure to decode a received vector).

Let's say I'm given a generator matrix G and a received vector v = (1, 1, 1, 0, 1, 0). How can I decode the received vector?

Here is what I would do, but I'm not sure:

1. Bring G to standard form (I | A)


2. Parity check matrix is: $H = (-A^t | I)$
   


3. Compute $v cdot H^t$, the received code is the one which has been encoded.

Is this correct?

Thanks for any correction!

abstract-algebra finite-fields coding-theory

share|cite|improve this question

asked Mar 14 at 11:50

JohnDJohnD

307112

$endgroup$

• 
  
  
  

  
  

  
  
  
  
  
  

  
  $begingroup$
  $v cdot H^t$ is not the "one which has been encoded", it is the syndrome of the error pattern from which one needs to determine what the error pattern was. Many different error patterns will ;produce the same syndrome and the decoder's job is to determine which is the most likely one (hint: fewer errors are more likely than many errors.
  $endgroup$
  – Dilip Sarwate
  Mar 17 at 19:53
  

  
  
  
  

add a comment | 

0

$begingroup$

I have a conceptional question to the concept of "syndrome decoding" (i.e. the procedure to decode a received vector).

Let's say I'm given a generator matrix G and a received vector v = (1, 1, 1, 0, 1, 0). How can I decode the received vector?

Here is what I would do, but I'm not sure:

1. Bring G to standard form (I | A)


2. Parity check matrix is: $H = (-A^t | I)$
   


3. Compute $v cdot H^t$, the received code is the one which has been encoded.

Is this correct?

Thanks for any correction!

abstract-algebra finite-fields coding-theory

share|cite|improve this question

asked Mar 14 at 11:50

JohnDJohnD

307112

$endgroup$

• 
  
  
  

  
  

  
  
  
  
  
  

  
  $begingroup$
  $v cdot H^t$ is not the "one which has been encoded", it is the syndrome of the error pattern from which one needs to determine what the error pattern was. Many different error patterns will ;produce the same syndrome and the decoder's job is to determine which is the most likely one (hint: fewer errors are more likely than many errors.
  $endgroup$
  – Dilip Sarwate
  Mar 17 at 19:53
  

  
  
  
  

add a comment | 

$begingroup$

I have a conceptional question to the concept of "syndrome decoding" (i.e. the procedure to decode a received vector).

Let's say I'm given a generator matrix G and a received vector v = (1, 1, 1, 0, 1, 0). How can I decode the received vector?

Here is what I would do, but I'm not sure:

1. Bring G to standard form (I | A)


2. Parity check matrix is: $H = (-A^t | I)$
   


3. Compute $v cdot H^t$, the received code is the one which has been encoded.

Is this correct?

Thanks for any correction!

abstract-algebra finite-fields coding-theory

share|cite|improve this question

asked Mar 14 at 11:50

JohnDJohnD

307112

$endgroup$

share|cite|improve this question

asked Mar 14 at 11:50

JohnDJohnD

307112

share|cite|improve this question

asked Mar 14 at 11:50

JohnDJohnD

307112

asked Mar 14 at 11:50

JohnDJohnD

307112

asked Mar 14 at 11:50

JohnDJohnD

307112

1 Answer
1

active

oldest

votes

1

$begingroup$

Well, its incomplete.
Take the received word $v$ and compute the syndrome $s = Hv^t$.

Here you need to do some preliminary work.
Write $v=c+e$ for codeword $c$ and error vector $e$. Then $Hv^t = Hc^t+ He^t = He^t$. Thus the syndrome $s$ tells you the error vector $e$. Then $c=v-e$ gives the decoded codeword. To do so, you need to make a list of pairs $(s, e)$ where $s$ is a syndrome and $e$ is a vector (coset leader) with $s=He^t$ of minimal Hamming weight. Note that there are cases where $e$ is not uniquely determined by $s$.

share|cite|improve this answer

answered Mar 14 at 13:34

WuestenfuxWuestenfux

5,2781513

$endgroup$

• 
  
  
  

  
  

  
  
  
  
  
  

  
  $begingroup$
  Thank you for your answer! I found here some examples, too: homepages.math.uic.edu/~leon/mcs425-s08/handouts/…
  $endgroup$
  – JohnD
  Mar 15 at 12:12
  

  
  
  
  


• 
  
  
  

  
  

  
  
  
  
  
  

  
  $begingroup$
  What I don't get: How are the coset leader(s) determined?
  $endgroup$
  – JohnD
  Mar 15 at 12:12
  

  
  
  
  


• 
  
  
  

  
  

  
  
  
  
  
  

  
  $begingroup$
  I think it requires enumeration.
  $endgroup$
  – Wuestenfux
  Mar 15 at 12:15
  

  
  
  
  

add a comment | 

Your Answer

StackExchange.ifUsing("editor", function () {
return StackExchange.using("mathjaxEditing", function () {
StackExchange.MarkdownEditor.creationCallbacks.add(function (editor, postfix) {
StackExchange.mathjaxEditing.prepareWmdForMathJax(editor, postfix, [["$", "$"], ["\\(","\\)"]]);
});
});
}, "mathjax-editing");

StackExchange.ready(function() {
var channelOptions = {
tags: "".split(" "),
id: "69"
};
initTagRenderer("".split(" "), "".split(" "), channelOptions);

StackExchange.using("externalEditor", function() {
// Have to fire editor after snippets, if snippets enabled
if (StackExchange.settings.snippets.snippetsEnabled) {
StackExchange.using("snippets", function() {
createEditor();
});
}
else {
createEditor();
}
});

function createEditor() {
StackExchange.prepareEditor({
heartbeatType: 'answer',
autoActivateHeartbeat: false,
convertImagesToLinks: true,
noModals: true,
showLowRepImageUploadWarning: true,
reputationToPostImages: 10,
bindNavPrevention: true,
postfix: "",
imageUploader: {
brandingHtml: "Powered by u003ca class="icon-imgur-white" href="https://imgur.com/"u003eu003c/au003e",
contentPolicyHtml: "User contributions licensed under u003ca href="https://creativecommons.org/licenses/by-sa/3.0/"u003ecc by-sa 3.0 with attribution requiredu003c/au003e u003ca href="https://stackoverflow.com/legal/content-policy"u003e(content policy)u003c/au003e",
allowUrls: true
},
noCode: true, onDemand: true,
discardSelector: ".discard-answer"
,immediatelyShowMarkdownHelp:true
});


}
});

draft saved

draft discarded

Sign up or log in

StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});

Sign up using Google

Sign up using Facebook

Sign up using Email and Password

Post as a guest

Name

Email

Required, but never shown

StackExchange.ready(
function () {
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fmath.stackexchange.com%2fquestions%2f3147906%2fsyndrome-decoding%23new-answer', 'question_page');
}
);

Post as a guest

Name

Email

Required, but never shown

1

$begingroup$

Well, its incomplete.
Take the received word $v$ and compute the syndrome $s = Hv^t$.

Here you need to do some preliminary work.
Write $v=c+e$ for codeword $c$ and error vector $e$. Then $Hv^t = Hc^t+ He^t = He^t$. Thus the syndrome $s$ tells you the error vector $e$. Then $c=v-e$ gives the decoded codeword. To do so, you need to make a list of pairs $(s, e)$ where $s$ is a syndrome and $e$ is a vector (coset leader) with $s=He^t$ of minimal Hamming weight. Note that there are cases where $e$ is not uniquely determined by $s$.

share|cite|improve this answer

answered Mar 14 at 13:34

WuestenfuxWuestenfux

5,2781513

$endgroup$

• 
  
  
  

  
  

  
  
  
  
  
  

  
  $begingroup$
  Thank you for your answer! I found here some examples, too: homepages.math.uic.edu/~leon/mcs425-s08/handouts/…
  $endgroup$
  – JohnD
  Mar 15 at 12:12
  

  
  
  
  


• 
  
  
  

  
  

  
  
  
  
  
  

  
  $begingroup$
  What I don't get: How are the coset leader(s) determined?
  $endgroup$
  – JohnD
  Mar 15 at 12:12
  

  
  
  
  


• 
  
  
  

  
  

  
  
  
  
  
  

  
  $begingroup$
  I think it requires enumeration.
  $endgroup$
  – Wuestenfux
  Mar 15 at 12:15
  

  
  
  
  

add a comment | 

1

$begingroup$

Well, its incomplete.
Take the received word $v$ and compute the syndrome $s = Hv^t$.

Here you need to do some preliminary work.
Write $v=c+e$ for codeword $c$ and error vector $e$. Then $Hv^t = Hc^t+ He^t = He^t$. Thus the syndrome $s$ tells you the error vector $e$. Then $c=v-e$ gives the decoded codeword. To do so, you need to make a list of pairs $(s, e)$ where $s$ is a syndrome and $e$ is a vector (coset leader) with $s=He^t$ of minimal Hamming weight. Note that there are cases where $e$ is not uniquely determined by $s$.

share|cite|improve this answer

answered Mar 14 at 13:34

WuestenfuxWuestenfux

5,2781513

$endgroup$

• 
  
  
  

  
  

  
  
  
  
  
  

  
  $begingroup$
  Thank you for your answer! I found here some examples, too: homepages.math.uic.edu/~leon/mcs425-s08/handouts/…
  $endgroup$
  – JohnD
  Mar 15 at 12:12
  

  
  
  
  


• 
  
  
  

  
  

  
  
  
  
  
  

  
  $begingroup$
  What I don't get: How are the coset leader(s) determined?
  $endgroup$
  – JohnD
  Mar 15 at 12:12
  

  
  
  
  


• 
  
  
  

  
  

  
  
  
  
  
  

  
  $begingroup$
  I think it requires enumeration.
  $endgroup$
  – Wuestenfux
  Mar 15 at 12:15
  

  
  
  
  

add a comment | 

$begingroup$

Well, its incomplete.
Take the received word $v$ and compute the syndrome $s = Hv^t$.

Here you need to do some preliminary work.
Write $v=c+e$ for codeword $c$ and error vector $e$. Then $Hv^t = Hc^t+ He^t = He^t$. Thus the syndrome $s$ tells you the error vector $e$. Then $c=v-e$ gives the decoded codeword. To do so, you need to make a list of pairs $(s, e)$ where $s$ is a syndrome and $e$ is a vector (coset leader) with $s=He^t$ of minimal Hamming weight. Note that there are cases where $e$ is not uniquely determined by $s$.

share|cite|improve this answer

answered Mar 14 at 13:34

WuestenfuxWuestenfux

5,2781513

$endgroup$

share|cite|improve this answer

answered Mar 14 at 13:34

WuestenfuxWuestenfux

5,2781513

answered Mar 14 at 13:34

WuestenfuxWuestenfux

5,2781513

answered Mar 14 at 13:34

WuestenfuxWuestenfux

5,2781513