1

I have to find the number of codes with maximum codeword length $n$ over an alphabet $S$ of size $r$.

The back of my book uses the fact that this number is equal to the number of subsets of $S_n$ and proceeds from there.

Could someone explain to me why this is the case? The textbook has not covered subsets yet, so I am wondering what the connection between the two is.

Thank you.

Silvia Rossi
  • 800
  • Can you explain what code is and what the set $S_n$ denotes? – Anguepa Jan 23 '18 at 00:35
  • Yes, a code is a set of strings over an alphabet and $S_n$ denotes the set of strings of length $n$ or less. @Anguepa – Silvia Rossi Jan 23 '18 at 00:39
  • @SilviaRossi I would have liked it if you had given me a reply-before just deleting the question: https://math.stackexchange.com/questions/2623915/monthly-effective-interest-rate-to-6-month-effective-interest-rate – callculus42 Jan 27 '18 at 20:21
  • @callculus Undeleted, I am very sorry about that. I had also posted it to quant.stackexchange and got mixed up between the comment notifications. – Silvia Rossi Jan 27 '18 at 20:33
  • @SilviaRossi OK, no problem. I appreciate that you have given a reply here. – callculus42 Jan 27 '18 at 20:35

1 Answers1

2

You have to prove that:
1- every subset of $S_n $ is a suitable code.
2- every suitable code is included in $S_n $

1- let $A\subseteq S_n $, now let $w\in A $ a string in the code A, $w\in A\rightarrow w\in S_n\rightarrow (|w|\leq n \wedge w\in S^*) $ as desired.

2- let $A=\{w\in S|w\leq n\}$ a code of suitable strings $w\in A\rightarrow w\in S_n $.

So we are done.

Note that all the implications simply come from the definitions given (remember $S_n=\{w\in S^*\|w|\leq n\} $).

Lucio Tanzini
  • 1,395