Dtjytyk

How dangerous is XSS?

How would I stat a creature to be immune to everything but the Magic Missile spell? (just for fun)

Short story with a alien planet, government officials must wear exploding medallions

Bullying boss launched a smear campaign and made me unemployable

Intersection Puzzle

Is there an expression that means doing something right before you will need it rather than doing it in case you might need it?

Examples of smooth manifolds admitting inbetween one and a continuum of complex structures

Why was the shrinking from 8″ made only to 5.25″ and not smaller (4″ or less)?

Ambiguity in the definition of entropy

Venezuelan girlfriend wants to travel the USA to be with me. What is the process?

iPad being using in wall mount battery swollen

Forgetting the musical notes while performing in concert

What is a romance in Latin?

What's the in-universe reasoning behind sorcerers needing material components?

What reasons are there for a Capitalist to oppose a 100% inheritance tax?

Is it logically or scientifically possible to artificially send energy to the body?

Is "remove commented out code" correct English?

ssTTsSTtRrriinInnnnNNNIiinngg

Mathematica command that allows it to read my intentions

How do I gain back my faith in my PhD degree?

Why didn't Boeing produce its own regional jet?

How much of data wrangling is a data scientist's job?

Which is the best way to check return result?

How do I deal with an unproductive colleague in a small company?

Error probability of repetition code

Explicit formula for Nth string of Gray Code.Can we find eight points which all have Hamming distance two?Help with total probability of a transmitted message (Total probability?)A set of words from a code has been received with up to 1 error, use a parity-check matrix to correct them.How can it be proven that gray code is the only possible way to arrange points in a 2^n graph with consecutive points only seperated by 1 bit?Coding theory - Syndromes errorSyndrome decoding and error correctionDesign the best schemes in terms of information transmission speedHow to find actual code based on parity check matrix, generator matrix and received code?Comparison of two Huffman codes:

0

$begingroup$

I am very lost. I would like to know how I calculate the probability of finding errors in repetition code.

For example say the codewords are 111 or 000 and probability of an error is 0.1. How would I find the probability of having one error in the transmitted codeword? i.e the chance that 000 becomes 001, 010, 100 or 111 becomes 110, 101, 011?

Am I correct to believe that this formula is the answer?
Where P is the probability 0.1

$$3p^{2}(1 − p) + p^{3} = 0.028$$

If so, how would I compute the chance of receiving a codeword with one error with a repetition code of (4,1) or (5,1), (6,1) etc. I cannot find any examples that make this clear or if I'm even on the right tracks.

probability coding-theory

share|cite|improve this question

edited Mar 19 at 15:33

Dilip Sarwate

19.4k13077

asked Mar 18 at 20:04

user3732999user3732999

31

$endgroup$

• 
  
  
  

  
  

  
  
  
  
  
  

  
  $begingroup$
  Welcome to Mathematics Stack Exchange! A quick tour will enhance your experience. Here are helpful tips to write a good question and write a good answer. For equations, please use MathJax.
  $endgroup$
  – dantopa
  Mar 18 at 20:05
  

  
  
  
  

add a comment | 

0

$begingroup$

I am very lost. I would like to know how I calculate the probability of finding errors in repetition code.

For example say the codewords are 111 or 000 and probability of an error is 0.1. How would I find the probability of having one error in the transmitted codeword? i.e the chance that 000 becomes 001, 010, 100 or 111 becomes 110, 101, 011?

Am I correct to believe that this formula is the answer?
Where P is the probability 0.1

$$3p^{2}(1 − p) + p^{3} = 0.028$$

If so, how would I compute the chance of receiving a codeword with one error with a repetition code of (4,1) or (5,1), (6,1) etc. I cannot find any examples that make this clear or if I'm even on the right tracks.

probability coding-theory

share|cite|improve this question

edited Mar 19 at 15:33

Dilip Sarwate

19.4k13077

asked Mar 18 at 20:04

user3732999user3732999

31

$endgroup$

• 
  
  
  

  
  

  
  
  
  
  
  

  
  $begingroup$
  Welcome to Mathematics Stack Exchange! A quick tour will enhance your experience. Here are helpful tips to write a good question and write a good answer. For equations, please use MathJax.
  $endgroup$
  – dantopa
  Mar 18 at 20:05
  

  
  
  
  

add a comment | 

$begingroup$

I am very lost. I would like to know how I calculate the probability of finding errors in repetition code.

For example say the codewords are 111 or 000 and probability of an error is 0.1. How would I find the probability of having one error in the transmitted codeword? i.e the chance that 000 becomes 001, 010, 100 or 111 becomes 110, 101, 011?

Am I correct to believe that this formula is the answer?
Where P is the probability 0.1

$$3p^{2}(1 − p) + p^{3} = 0.028$$

If so, how would I compute the chance of receiving a codeword with one error with a repetition code of (4,1) or (5,1), (6,1) etc. I cannot find any examples that make this clear or if I'm even on the right tracks.

probability coding-theory

share|cite|improve this question

edited Mar 19 at 15:33

Dilip Sarwate

19.4k13077

asked Mar 18 at 20:04

user3732999user3732999

31

$endgroup$

share|cite|improve this question

edited Mar 19 at 15:33

Dilip Sarwate

19.4k13077

asked Mar 18 at 20:04

user3732999user3732999

31

share|cite|improve this question

edited Mar 19 at 15:33

Dilip Sarwate

19.4k13077

asked Mar 18 at 20:04

user3732999user3732999

31

edited Mar 19 at 15:33

Dilip Sarwate

19.4k13077

edited Mar 19 at 15:33

Dilip Sarwate

19.4k13077

asked Mar 18 at 20:04

user3732999user3732999

31

asked Mar 18 at 20:04

user3732999user3732999

31

1 Answer
1

active

oldest

votes

2

$begingroup$

Am I correct to believe that this formula is the answer?

What you need is not to know "the formula", but where it comes from.

In $(3,1)$ repetition code, we code the 0 as 000. The decoding (assuming a BSC channel with crossover (bit error) probability $p<1/2$) is by majority: if, say, we receive 001 we decide that it's more probable that the trasmitted codeword was 000 than 111. Why? Because it's more probable to have a single bit error (000 $to$ 001 : last bit was changed) than having two (111 $to$ 001 : two first bit changed).

When does this decoding strategy fail? It should be clear that the decoding is wrong where there are indeed two bit-errors ... or three. If we trasmit 000 and the first and last bit are flipped, so we receive 101, the decode will guess : 111 and we'll have decoding error. Conclusion: the event "decoding error" is equivalent to the event "having more than half bit errors". The formula you copied computes this, the first term correspond to the 2-bits errors (there are 3 possible cases) and the last term for the 3-bits error.

If you understood the above, then you should be able to compute the probability of bad decoding for a repetition $(5,1)$ code (I've never seen a $(4,1)$ repetition code ; even lengths are avoided to get rid of ties).

share|cite|improve this answer

edited Mar 18 at 20:56

answered Mar 18 at 20:24

leonbloyleonbloy

42.1k647108

$endgroup$

• 
  
  
  

  
  

  
  
  
  
  
  

  
  $begingroup$
  I do believe that I can make sense of that, thank you. I understood the formula but you are right, I needed to know where it comes from so I could work with different repetition codes. I could not find any examples that explained this as clearly as you have.
  $endgroup$
  – user3732999
  Mar 18 at 20:34
  
  
  

  
  
  
  

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%2f3153247%2ferror-probability-of-repetition-code%23new-answer', 'question_page');
}
);

Post as a guest

Name

Email

Required, but never shown

2

$begingroup$

Am I correct to believe that this formula is the answer?

What you need is not to know "the formula", but where it comes from.

In $(3,1)$ repetition code, we code the 0 as 000. The decoding (assuming a BSC channel with crossover (bit error) probability $p<1/2$) is by majority: if, say, we receive 001 we decide that it's more probable that the trasmitted codeword was 000 than 111. Why? Because it's more probable to have a single bit error (000 $to$ 001 : last bit was changed) than having two (111 $to$ 001 : two first bit changed).

When does this decoding strategy fail? It should be clear that the decoding is wrong where there are indeed two bit-errors ... or three. If we trasmit 000 and the first and last bit are flipped, so we receive 101, the decode will guess : 111 and we'll have decoding error. Conclusion: the event "decoding error" is equivalent to the event "having more than half bit errors". The formula you copied computes this, the first term correspond to the 2-bits errors (there are 3 possible cases) and the last term for the 3-bits error.

If you understood the above, then you should be able to compute the probability of bad decoding for a repetition $(5,1)$ code (I've never seen a $(4,1)$ repetition code ; even lengths are avoided to get rid of ties).

share|cite|improve this answer

edited Mar 18 at 20:56

answered Mar 18 at 20:24

leonbloyleonbloy

42.1k647108

$endgroup$

• 
  
  
  

  
  

  
  
  
  
  
  

  
  $begingroup$
  I do believe that I can make sense of that, thank you. I understood the formula but you are right, I needed to know where it comes from so I could work with different repetition codes. I could not find any examples that explained this as clearly as you have.
  $endgroup$
  – user3732999
  Mar 18 at 20:34
  
  
  

  
  
  
  

add a comment | 

2

$begingroup$

Am I correct to believe that this formula is the answer?

What you need is not to know "the formula", but where it comes from.

In $(3,1)$ repetition code, we code the 0 as 000. The decoding (assuming a BSC channel with crossover (bit error) probability $p<1/2$) is by majority: if, say, we receive 001 we decide that it's more probable that the trasmitted codeword was 000 than 111. Why? Because it's more probable to have a single bit error (000 $to$ 001 : last bit was changed) than having two (111 $to$ 001 : two first bit changed).

When does this decoding strategy fail? It should be clear that the decoding is wrong where there are indeed two bit-errors ... or three. If we trasmit 000 and the first and last bit are flipped, so we receive 101, the decode will guess : 111 and we'll have decoding error. Conclusion: the event "decoding error" is equivalent to the event "having more than half bit errors". The formula you copied computes this, the first term correspond to the 2-bits errors (there are 3 possible cases) and the last term for the 3-bits error.

If you understood the above, then you should be able to compute the probability of bad decoding for a repetition $(5,1)$ code (I've never seen a $(4,1)$ repetition code ; even lengths are avoided to get rid of ties).

share|cite|improve this answer

edited Mar 18 at 20:56

answered Mar 18 at 20:24

leonbloyleonbloy

42.1k647108

$endgroup$

• 
  
  
  

  
  

  
  
  
  
  
  

  
  $begingroup$
  I do believe that I can make sense of that, thank you. I understood the formula but you are right, I needed to know where it comes from so I could work with different repetition codes. I could not find any examples that explained this as clearly as you have.
  $endgroup$
  – user3732999
  Mar 18 at 20:34
  
  
  

  
  
  
  

add a comment | 

$begingroup$

Am I correct to believe that this formula is the answer?

What you need is not to know "the formula", but where it comes from.

In $(3,1)$ repetition code, we code the 0 as 000. The decoding (assuming a BSC channel with crossover (bit error) probability $p<1/2$) is by majority: if, say, we receive 001 we decide that it's more probable that the trasmitted codeword was 000 than 111. Why? Because it's more probable to have a single bit error (000 $to$ 001 : last bit was changed) than having two (111 $to$ 001 : two first bit changed).

When does this decoding strategy fail? It should be clear that the decoding is wrong where there are indeed two bit-errors ... or three. If we trasmit 000 and the first and last bit are flipped, so we receive 101, the decode will guess : 111 and we'll have decoding error. Conclusion: the event "decoding error" is equivalent to the event "having more than half bit errors". The formula you copied computes this, the first term correspond to the 2-bits errors (there are 3 possible cases) and the last term for the 3-bits error.

If you understood the above, then you should be able to compute the probability of bad decoding for a repetition $(5,1)$ code (I've never seen a $(4,1)$ repetition code ; even lengths are avoided to get rid of ties).

share|cite|improve this answer

edited Mar 18 at 20:56

answered Mar 18 at 20:24

leonbloyleonbloy

42.1k647108

$endgroup$

share|cite|improve this answer

edited Mar 18 at 20:56

answered Mar 18 at 20:24

leonbloyleonbloy

42.1k647108

answered Mar 18 at 20:24

leonbloyleonbloy

42.1k647108

answered Mar 18 at 20:24

leonbloyleonbloy

42.1k647108