A phone stores photographs, messages and videos as digital information. Why can some files be made much smaller while others hardly shrink at all? And why do computer scientists talk about information in bits?
These questions lead to an unexpected use of logarithms.
Additional Mathematics provides the algebraic foundation for understanding how the number of possible messages relates to the number of binary choices needed to represent them.
A logarithm tells us how many repeated multiplications are needed to reach a given value. In a binary representation, that becomes a way to count the number of yes-or-no choices required to distinguish among possibilities.
This article connects exponents, logarithms, counting, probability and the introductory ideas of information theory. Formal coding theory and entropy are enrichment beyond the Singapore G3 Additional Mathematics syllabus, but the underlying log laws are directly relevant to the subject.
The goal is to understand why the mathematics works, not to promise that every file can be compressed or that one simple code is suitable for a real application.
Start with binary choices
Suppose a question has only two possible answers:
Yes or no.
One binary choice can distinguish between those two answers.
In digital terminology, a bit has two possible states, commonly written:
0 and 1.
If we have two independent bit positions, the number of possible binary strings is:
2 × 2 = 4.
They are:
00,
01,
10,
11.
Three positions give:
2³ = 8
possible strings.
Four positions give:
2⁴ = 16.
In general, n binary positions give:
2^n
possible fixed-length strings.
This is a direct application of the multiplication principle and index laws.
Why the exponent counts positions
Imagine building a string one position at a time.
For the first bit, there are two choices.
For the second, another two.
For the third, another two.
The number of complete combinations is the product of the choices.
For n positions:
2 × 2 × … × 2 = 2^n.
The exponent n counts how many independent binary positions are available in the encoding.
This does not mean every possible string must be used.
It tells us the maximum number of distinct labels that a fixed n-bit code can assign when all binary strings are available.
Additional Mathematics students learn to reason from a repeated multiplication rule to a power.
The next step is to reverse the question.
How many bits do we need?
Suppose we have N different objects or symbols that each need a distinct fixed-length binary label.
A code with b bits can assign at most:
2^b
different labels.
Therefore we need:
2^b ≥ N.
Take base-two logarithms:
b ≥ log₂N.
But b must be an integer number of bit positions.
Therefore the smallest suitable fixed length is:
b = ceiling(log₂N),
where “ceiling” means round upwards to the next integer if the value is not already an integer.
This is not ordinary rounding to the nearest whole number.
It is a capacity condition.
If the number of available strings is too small, some symbols cannot receive distinct labels.
A thousand possible labels
Suppose a system needs one unique fixed-length binary label for each of one thousand possibilities.
How many bits are necessary?
We know:
2⁹ = 512.
And:
2¹⁰ = 1024.
Nine bits provide only 512 distinct strings, which is insufficient.
Ten bits provide 1024, which is enough.
Therefore the minimum fixed length is:
10 bits.
The logarithm calculation gives:
log₂1000 ≈ 9.966.
Taking the ceiling gives ten.
The capacity has twenty-four unused combinations if exactly one thousand labels are assigned.
That is acceptable.
A fixed-length code need not use every possible bit pattern.
Use the change-of-base formula
Some calculators have natural logarithms and common logarithms but no dedicated log-base-two key.
Additional Mathematics teaches change of base:
log₂N = ln N/ln 2.
For N = 1000:
log₂1000 = ln 1000/ln 2.
This is approximately 9.9658.
Therefore ten bit positions are needed for one thousand fixed labels.
The calculation illustrates why logarithms are useful when the unknown appears in an exponent.
We began with:
2^b ≥ N.
The logarithm converted the capacity inequality into a condition on b.
The integer restriction then completed the interpretation.
A twenty-six-symbol alphabet
Suppose an illustrative code must represent twenty-six distinct uppercase-letter symbols.
Four bits give:
2⁴ = 16
possible strings.
That is not enough.
Five bits give:
2⁵ = 32.
That is enough.
So a simple fixed-length representation needs five bits per symbol under this toy model.
A message of one hundred such symbols would occupy:
100 × 5 = 500 bits
if each symbol is represented directly by its five-bit label, ignoring all headers, framing and other data.
The calculation is a coding-capacity example.
It is not a claim about how a real text file or a particular character encoding stores uppercase letters.
Actual digital formats include additional rules and context.
Compare five-bit and eight-bit labels
Suppose our toy system uses only twenty-six possible symbols.
A fixed five-bit code uses 500 bits for one hundred symbols.
A fixed eight-bit code would use:
100 × 8 = 800 bits.
The numerical difference is:
300 bits.
The five-bit code is more compact for this narrowly defined alphabet and representation.
But a real system may need lowercase letters, punctuation, multilingual characters or control symbols.
It may also require interoperability with existing encodings.
Therefore fewer bits in a toy example do not automatically mean a practical text format should use that exact scheme.
A-Math gives us the counting calculation.
Software design determines which symbols and other constraints must be supported.
Equal-length codes are easy to decode
Suppose our code uses two bits for four symbols:
A = 00,
B = 01,
C = 10,
D = 11.
Each symbol has the same length.
A message is decoded by splitting the bit sequence into two-bit blocks.
For example:
000110
can be divided as:
00 01 10.
Therefore the message is:
ABC.
The fixed length tells us where one symbol ends and the next begins.
There is no ambiguity about boundaries if decoding begins at the correct position and the code structure is known.
This simplicity is one reason fixed-length codes are useful for teaching.
But equal lengths may use more bits than necessary when some symbols are much more common than others.
What if symbols occur at different frequencies?
Imagine a toy source with four symbols:
A, B, C and D.
Suppose their probabilities are:
P(A) = 1/2.
P(B) = 1/4.
P(C) = 1/8.
P(D) = 1/8.
The probabilities add to one:
1/2 + 1/4 + 1/8 + 1/8 = 1.
Symbol A occurs half the time on average in this assumed source.
B occurs one-quarter of the time.
C and D are less common.
A two-bit fixed-length code uses two bits for every symbol, regardless of frequency.
Could we use shorter codes for common symbols and longer ones for rare symbols?
Yes, if the code remains decodable.
Construct a variable-length code
Consider these assignments:
A = 0.
B = 10.
C = 110.
D = 111.
The code lengths are:
A: one bit.
B: two bits.
C: three bits.
D: three bits.
The commonest symbol gets the shortest code.
The rarest symbols get longer codes.
But why can the receiver know where one codeword ends?
The key property is that no assigned codeword is the beginning, or prefix, of another assigned codeword.
Such a code is called prefix-free.
This property allows the concatenated bitstream to be decoded as the symbols arrive, using the known code dictionary.
Check the prefix-free property
Our codewords are:
0,
10,
110,
111.
The codeword 0 is not the beginning of any other codeword because the others begin with 1.
The codeword 10 is not the beginning of 110 or 111, which begin with 11.
The codeword 110 is not a prefix of 111.
Therefore no codeword is a prefix of another.
That is enough to establish the prefix-free property.
A decoder can recognise 0 immediately as A.
If the first bit is 1, it reads another bit.
The pattern 10 gives B.
If the first two bits are 11, a third bit distinguishes C from D.
This branching structure explains why short and long codewords can coexist without ambiguous boundaries.
Encode a sample eight-symbol message
Consider the message:
AAAABBCD.
It contains:
Four A symbols.
Two B symbols.
One C.
One D.
Using our variable code:
A contributes one bit each.
B contributes two bits each.
C contributes three bits.
D contributes three bits.
The total encoded length is:
4(1) + 2(2) + 1(3) + 1(3).
Therefore:
4 + 4 + 3 + 3 = 14 bits.
With an ordinary fixed two-bit code for four symbols, the same eight-symbol message would use:
8 × 2 = 16 bits.
The variable code saves two bits in this example.
That is a modest but clear saving.
Decode the message to verify it
The encoded sequence for AAAABBCD can be grouped as:
0 0 0 0 10 10 110 111.
Concatenated, the sequence is fourteen bits long.
Decoding begins at the left.
Each zero at the start is immediately interpreted as A.
The next codeword beginning with 10 is B.
The next 10 is another B.
The remaining patterns 110 and 111 represent C and D.
The decoder reconstructs:
AAAABBCD.
The message is recovered exactly.
This is a simple example of lossless encoding.
Its purpose is to demonstrate reversible representation, not to provide a complete file format.
Compute expected bits per symbol
We do not normally know the exact order of future symbols.
But if the probabilities are known and the source behaves according to the assumed distribution, we can calculate expected code length.
Let L be the codeword length of a randomly selected symbol.
The expectation is:
E[L] = P(A)(1) + P(B)(2) + P(C)(3) + P(D)(3).
Substitute:
E[L] = (1/2)(1) + (1/4)(2) + (1/8)(3) + (1/8)(3).
Calculate:
1/2 + 1/2 + 3/8 + 3/8.
Therefore:
E[L] = 7/4 = 1.75 bits per symbol.
The fixed-length code uses exactly two bits per symbol.
The variable code’s expected length is lower for this particular probability distribution.
Why one message does not guarantee the average
Our eight-symbol example used fourteen bits.
That is exactly:
14/8 = 1.75 bits per symbol.
But another eight-symbol message might be:
AAAAAAAA.
Its encoded length would be eight bits.
A different message might contain only C and D symbols.
Then it would use:
8 × 3 = 24 bits.
The expected length of 1.75 bits per symbol is an average under the assumed probability distribution.
It is not a promise that every individual message becomes shorter.
This distinction is important in probability and data compression.
A useful average does not determine every possible outcome.
A-Math gives students the algebra and ratio reasoning to interpret such claims carefully.
Entropy turns probabilities into information
Information theory defines a measure of information associated with an event of probability p:
I = -log₂p,
for 0 < p ≤ 1.
An event with probability one has:
I = -log₂1 = 0 bits.
In this mathematical measure, a certain event carries no surprise about which outcome occurred.
An event with probability one-half has:
I = -log₂(1/2) = 1 bit.
An event with probability one-eighth has:
I = -log₂(1/8) = 3 bits.
Less probable events have greater information content under this definition.
The logarithm measures how unlikely an outcome was relative to the model.
This is not a measure of how emotionally important a message feels to a person.
Why a logarithm is natural for information
Suppose two independent events have probabilities p and q.
Their joint probability is:
pq.
The information assigned to the combined event is:
-log₂(pq).
Apply the product law of logarithms:
-log₂p – log₂q.
Therefore:
I(combined) = I(first) + I(second).
The information amounts add because independent probabilities multiply.
This is an elegant reason logarithms appear in information theory.
A mathematical measure of surprise is built to turn the multiplication of independent event probabilities into addition.
Additional Mathematics students already learn the algebra behind this transformation.
The application gives that algebra a new interpretation.
Calculate the information of our four symbols
Our toy probabilities are:
P(A) = 1/2.
P(B) = 1/4.
P(C) = 1/8.
P(D) = 1/8.
Their individual information values are:
I(A) = 1 bit.
I(B) = 2 bits.
I(C) = 3 bits.
I(D) = 3 bits.
These happen to equal the codeword lengths we assigned.
That is not a universal property of every possible probability distribution.
It works neatly here because each probability is an exact negative power of two.
The pattern makes the source especially convenient for an introductory example.
Define Shannon entropy
For a discrete source with probabilities p₁, p₂, …, pₙ, Shannon entropy in bits is:
H = -Σ p_i log₂p_i,
where the sum covers the possible outcomes and zero-probability terms are handled by their limiting convention.
Equivalently:
H = Σ p_i log₂(1/p_i).
It represents the average information content of a source symbol under the probability model.
For our four-symbol source:
H = (1/2)(1) + (1/4)(2) + (1/8)(3) + (1/8)(3).
Therefore:
H = 1.75 bits per symbol.
The number is the same as our variable code’s expected length.
Our simple prefix code matches the entropy in this specially chosen example.
Formal entropy and source-coding theorems are advanced topics, but the calculation uses elementary probabilities and logarithms.
Why the code reaches the entropy here
For each of our symbols:
P(symbol) = 2^(-length).
For A:
P(A) = 1/2 = 2⁻¹.
For B:
P(B) = 1/4 = 2⁻².
For C and D:
P = 1/8 = 2⁻³.
Therefore:
-log₂P(symbol) = codeword length.
Averaging those equal quantities gives the same result for entropy and expected length.
This is a particularly clean case.
In a general source, probabilities need not be exact powers of one-half, and the shortest prefix code for individual symbols may have an average length greater than entropy.
The lower-bound interpretation needs the assumptions of information theory, not merely a calculator result.
What a prefix code’s lengths must satisfy
For a binary prefix-free code with codeword lengths l₁, …, lₙ, the Kraft inequality states:
Σ 2^(-l_i) ≤ 1.
Our chosen code lengths are:
1, 2, 3, 3.
Calculate:
2⁻¹ + 2⁻² + 2⁻³ + 2⁻³.
That is:
1/2 + 1/4 + 1/8 + 1/8 = 1.
The lengths satisfy the inequality exactly.
This is consistent with a complete binary prefix tree in which the assigned leaves occupy all available branches in the corresponding structure.
We already verified the codewords directly.
The inequality provides a more general mathematical check on possible sets of prefix-code lengths.
Its proof and converse belong to more advanced coding theory.
A distribution change can remove the benefit
Suppose A, B, C and D are all equally likely:
P = 1/4 each.
A fixed two-bit code uses exactly two bits per symbol.
Our variable-length code still has lengths:
1, 2, 3, 3.
Its expected length under the new equal-probability distribution is:
(1/4)(1) + (1/4)(2) + (1/4)(3) + (1/4)(3).
Calculate:
(1 + 2 + 3 + 3)/4 = 9/4.
Therefore:
E[L] = 2.25 bits per symbol.
That is worse than the fixed two-bit code.
The same encoding scheme no longer provides an average saving.
This is why compression depends on the data distribution.
A code suited to one source may be inefficient for another.
Equal probabilities produce a different entropy
For four equally likely symbols:
p_i = 1/4.
Each symbol’s information content is:
-log₂(1/4) = 2 bits.
Therefore the entropy is:
H = 4(1/4)(2) = 2 bits per symbol.
The fixed two-bit code matches that entropy.
There is no need to favour one symbol with a shorter code if all four are equally likely and we encode one symbol at a time using this simple fixed-length arrangement.
The comparison demonstrates that the expected information depends on probabilities, not just on the number of possible symbols.
A-Math students can calculate both cases using the same logarithm laws.
The interpretation changes because the probability model changed.
A binary source can have less than one bit of entropy
Suppose a source produces a binary symbol with probabilities:
P(0) = 0.9.
P(1) = 0.1.
Its entropy is:
H = -0.9log₂0.9 – 0.1log₂0.1.
Numerically:
H ≈ 0.469 bits per symbol.
A fixed representation still uses one bit for each binary symbol.
The entropy is lower because the source is highly predictable.
But the number 0.469 is an average information measure, not a literal fractional physical bit stored for one isolated symbol.
Efficient coding over many symbols can approach the relevant entropy rate under appropriate conditions.
The full theory is more advanced than one-symbol coding.
This example shows why expected information and actual codeword length should not be confused.
Why a single binary event still needs a distinguishable representation
If a source can output either zero or one and both outcomes remain possible, a simple fixed one-symbol code needs two distinct codewords.
One-bit strings provide exactly two choices.
A fractional bit cannot directly be assigned as the length of an ordinary individual binary codeword.
Entropy below one bit per symbol becomes meaningful as an average over many outcomes or suitably constructed blocks under the required coding assumptions.
For example, a long sequence that contains mostly zeros may be represented efficiently by describing patterns rather than repeating each zero separately, provided the decoder can recover the exact sequence.
The details depend on the scheme.
The general lesson is that average information and the length of one particular digital label are different mathematical quantities.
Compression can use patterns, not just symbol frequency
Imagine a toy message that contains one thousand repeated A symbols.
Writing A one thousand times is a literal description.
A different representation might say:
“Repeat A one thousand times.”
The latter can be shorter if the encoding scheme efficiently represents the instruction and count.
This is an intuitive example of run-length style compression.
But the decoder must know what that instruction means.
The compressed message must also include any information required to recover the original sequence exactly.
The amount of saving depends on how the instruction and count are represented and how repetitive the data really are.
The mathematical theme is the same: predictable structure can sometimes reduce how much description is needed.
A run-length representation can also grow larger
Suppose a message alternates:
ABABABABAB…
If a run-length code stores each short run as a symbol followed by a count, it may use more bits than the original symbols.
The extra count fields create overhead.
Similarly, a source containing little exploitable structure may be difficult to compress with a simple method.
Therefore “compression” is not a universal promise of smaller output for every input.
A good scheme depends on the data and the intended application.
The Mathematics of counting possible strings helps explain why there are fundamental limitations.
Those limits are a natural place for logarithms and powers to reappear.
Why every possible file cannot be shortened losslessly
Consider all binary strings of exactly n bits.
There are:
2^n
such strings.
Now count all binary strings shorter than n bits.
There is:
1 string of length zero,
2 of length one,
4 of length two,
and so on up to length n – 1.
The total is the geometric sum:
1 + 2 + 4 + … + 2^(n-1).
This equals:
2^n – 1.
There are fewer distinct shorter strings than there are original n-bit strings.
Therefore no one-to-one mapping can assign a strictly shorter binary string to every possible n-bit input.
At least one input must fail to shrink under any lossless representation that assigns distinct shorter outputs in that manner.
This is a counting argument, not a statement about a specific commercial compression program.
Why unique recovery matters
Lossless compression means the original data can be recovered exactly from the stored representation under the decoding rules.
If two different source files receive the same complete compressed representation, a decoder cannot know which original file to reconstruct.
Therefore a valid lossless encoding must distinguish the different possible inputs within its scope.
This is why counting possible codewords matters.
We cannot place more different source messages into fewer distinct representations without losing unique recoverability.
A-Math students encounter the same logical structure when proving that a function cannot assign two different inputs to one invertible output without additional information.
The applications differ, but the reasoning about uniqueness is closely related.
Compression algorithms may have overhead
In our toy A-B-C-D example, we counted only the encoded symbol bits.
A real file may also need information about the code dictionary, file format, metadata, checksums or other structure.
If that overhead is large relative to a short message, the total compressed file may be larger than the original.
A mathematical saving of two bits for one eight-symbol message does not guarantee a smaller real file.
The codewords and the context must be known to the decoder somehow.
In a long stream using a pre-agreed code, the dictionary overhead may be negligible or shared.
In a small standalone file, it may dominate.
A useful numerical comparison must state what is included in the bit count.
Lossless and lossy compression answer different questions
Lossless compression reconstructs the original data exactly under the defined representation.
Lossy compression permits some change to the original representation in exchange for potentially greater reductions in stored size.
For example, some image or audio compression formats can discard or approximate information according to a chosen model of acceptable differences.
The mathematical challenge then changes.
Instead of requiring exact reconstruction, the system needs an agreed measure of distortion or quality.
Information theory includes more advanced ways of analysing that trade-off.
Those ideas are enrichment beyond SEC Additional Mathematics.
The important foundation is recognising that fewer bits can have different meanings depending on whether information must be preserved exactly.
Information content is not personal meaning
In Shannon’s mathematical framework, a rare outcome can carry more information than a common outcome because it is less predictable under the model.
That does not mean a rare message is more useful, truthful or emotionally important.
For example, a very predictable safety instruction can be extremely important to a person.
A random-looking string can carry many bits of information without having any meaningful interpretation.
Mathematical information content describes a probability-based property of an outcome.
It is not a universal measure of human value.
Students should learn to distinguish technical definitions from ordinary-language meanings, just as they distinguish mathematical “work”, “power” or “energy” from their everyday uses.
Count a sequence of independent fair choices
Suppose an experiment produces eight independent fair yes-or-no outcomes.
Each outcome has two possibilities.
The full sequence has:
2⁸ = 256
possible ordered results.
If the outcomes are fair and independent, each complete sequence has probability:
1/256.
The information content of any particular eight-outcome sequence is:
-log₂(1/256).
Because:
1/256 = 2⁻⁸,
the result is:
8 bits.
This is exactly one bit per independent fair binary outcome.
The example shows how probabilities multiply across independent events while information adds.
That relationship follows from the logarithm product rule.
Independence is an assumption, not automatic
Suppose the outcomes were not independent.
Perhaps the second bit always repeats the first.
Then there are only two possible two-bit sequences:
00,
and:
11.
If each is equally likely, one binary choice distinguishes them.
The apparent two positions do not contain two independent fair choices.
The information about the second position is determined by the first.
This illustrates why dependence can create compressible structure.
The number of physical positions is not necessarily equal to the amount of independent information.
A-Math students can understand the counting difference:
Four possible strings exist without the repetition restriction.
Only two are permitted under the stated dependency.
The underlying constraint changes the number of possibilities.
Conditional information and prediction
Suppose a learner knows the first symbol of a message.
If that knowledge changes the probabilities of later symbols, the expected information in the later symbols may change.
For example, if a source alternates deterministically between A and B, knowing the first symbol determines all later positions.
A naive symbol-by-symbol frequency count might not capture that predictability fully.
A more advanced encoder can exploit relationships across positions rather than only the frequency of individual symbols.
This leads towards conditional probabilities, entropy rates and sophisticated compression methods.
These subjects are not required for ordinary G3 Additional Mathematics.
But their foundations include familiar skills: counting possibilities, using logarithms and identifying dependencies.
The mathematical language grows naturally from these simple examples.
Another counting example: five decimal digits
Suppose a code consists of exactly five decimal digits, and leading zeroes are permitted.
Each position has ten possibilities.
Therefore the number of possible codes is:
10⁵ = 100000.
If we wanted a fixed-length binary label for every one of these possible digit strings, we would require:
2^b ≥ 100000.
Take logarithms:
b ≥ log₂100000.
Using change of base:
log₂100000 = ln 100000/ln 2.
This is approximately:
16.61.
Therefore:
b = 17 bits
is the smallest fixed binary length that can distinguish all one hundred thousand possibilities.
Sixteen bits provide only 65,536 labels.
Seventeen provide 131,072.
The calculation is a direct application of A-Math logarithms.
A code’s length is not the same as its security
The preceding example counted possible five-digit strings.
That counting fact does not by itself establish whether a real system is secure.
Security can depend on how codes are generated, how attempts are limited, whether codes are predictable, how they are transmitted and many other details.
A code with more possible labels may have a larger mathematical search space, but that is only one component of a broader security analysis.
This is another modelling limitation worth recognising.
An A-Math equation can calculate the number of possibilities precisely.
It cannot substitute for the full technical assumptions required to evaluate a security system.
The same caution applies whenever information theory is discussed through simplified examples.
Logarithms measure successive doubling
Consider a storage requirement that doubles every time a parameter increases by one.
A toy model is:
S(n) = S₀2^n.
Suppose we want to know when the storage reaches 64 times its initial value.
Write:
S₀2^n = 64S₀.
Divide by positive S₀:
2^n = 64.
Since 64 = 2⁶:
n = 6.
If the target were not an exact power of two, logarithms would give the threshold.
This is related to the counting of possible bit strings.
The same exponential growth that increases representational capacity also explains why exhaustive data sets can become large as more independent binary choices are added.
A fixed increase in bits multiplies capacity
Suppose a fixed-length encoding gains one additional bit.
Its capacity changes from:
2^n
to:
2^(n+1).
The ratio is:
2^(n+1)/2^n = 2.
So one extra bit doubles the number of available codewords.
Two extra bits multiply capacity by four.
Three extra bits multiply capacity by eight.
This is an exact power law.
It does not mean the amount of human-understandable content necessarily doubles.
It means the number of distinct fixed-length binary patterns doubles.
Students should keep the counting interpretation clear.
A-Math develops the index laws needed to make this conclusion immediately.
Common mistake: rounding logarithms to the nearest integer
Suppose:
log₂1000 ≈ 9.966.
A student might round to ten, obtaining the right answer.
But that happens to work here.
For N = 600:
log₂600 ≈ 9.229.
Ordinary rounding to the nearest integer would give nine.
But nine bits have only:
2⁹ = 512
possible labels, which is not enough.
We need ten bits.
The correct rule is:
b = ceiling(log₂N).
The ceiling comes from the capacity inequality, not ordinary decimal rounding.
Understanding the condition is more reliable than memorising the answer for one example.
Common mistake: confusing bits per symbol with total bits
A code might average 1.75 bits per symbol under a probability model.
That does not mean a message with one hundred symbols is literally stored as a fractional number of bits.
A particular encoded message has an integer number of bits.
The expected length of one hundred symbols may be:
100 × 1.75 = 175 bits
under an appropriate model where the per-symbol expectation applies.
But individual sequences may use more or fewer bits.
The expected value is an average over possible messages.
Students should distinguish probability-weighted averages from the exact length of one realised sequence.
This is a useful general mathematical habit.
Common mistake: assuming the commonest code must always be one bit
A shorter code for a frequent symbol can be useful, but the complete code must remain decodable.
There is no rule that every common symbol can be assigned a one-bit code simultaneously.
Only two distinct one-bit strings exist:
0 and 1.
If a prefix-free code uses both of them as complete codewords, no additional nonempty codeword can be added without violating the prefix condition.
The binary tree has no branches left for longer codewords under those prefixes.
Therefore codeword lengths must be planned as a complete set.
A-Math counting and exponent reasoning helps explain these structural restrictions.
Common mistake: assuming every file can be compressed
Some inputs have obvious repetition.
Others have little exploitable redundancy for a given encoding model.
The counting argument shows that no lossless one-to-one scheme can make every possible n-bit input strictly shorter.
A student who claims universal shortening is making a mathematically impossible promise.
The repair is to distinguish average compression for a specified source distribution from a guarantee about every possible input.
A compression method can perform well on some classes of data while expanding others.
The correct statement is conditional.
That is an important example of how mathematical proof can clarify claims about technology.
A five-session study plan
Session one: count binary possibilities
Write all two-bit patterns.
Derive 2^n possibilities for n fixed binary positions.
Calculate the minimum bits needed for twenty-six and one thousand labels.
Session two: practise logarithms
Use the change-of-base formula to evaluate log₂N.
Explain why the minimum fixed length uses a ceiling rather than nearest-integer rounding.
Session three: build a prefix code
Use A = 0, B = 10, C = 110 and D = 111.
Encode AAAABBCD.
Check that its length is fourteen bits and that it decodes uniquely.
Session four: calculate expected length and entropy
Use probabilities one-half, one-quarter, one-eighth and one-eighth.
Calculate the expected code length and Shannon entropy.
Compare with a uniform four-symbol source.
Session five: investigate limits
Count the number of binary strings shorter than n bits.
Explain why no lossless encoding can shorten every possible n-bit string.
Then distinguish lossless compression, lossy compression and the role of model assumptions.
The aim is mathematical understanding, not professional compressor implementation.
What parents can ask during revision
Ask why n bits provide 2^n possible strings.
Ask how many bits are needed for one thousand distinct labels.
Ask why a shorter code for a common symbol might reduce average length.
Ask how the decoder knows where a variable-length codeword ends.
Ask whether an average of 1.75 bits means one actual symbol can occupy three-quarters of a bit.
Ask why every possible message cannot be made shorter without losing information.
These questions encourage students to explain the counting and logarithms.
A learner who can derive the bit-capacity inequality independently has gained a useful quantitative insight.
Singapore Additional Mathematics context
The official 2027 Singapore-Cambridge Secondary Education Certificate G3 Additional Mathematics syllabus K341 includes exponential and logarithmic functions, logarithm laws, change of base and mathematical modelling.
Those foundations support the bit-counting examples here.
Shannon entropy, Kraft’s inequality, prefix coding and formal information theory are enrichment concepts, not separately asserted examination topics in G3 Additional Mathematics.
Students should consult the official SEAB 2027 G3 syllabus directory for the precise assessed requirements.
For deeper research-based learning, MIT OpenCourseWare’s Information Theory lecture notes cover entropy, source coding and optimal codes. The MIT lecture on data compression and Shannon entropy offers another advanced reference.
How a three-student tutorial can help
One learner may know logarithm laws but round a bit-capacity calculation the wrong way.
Another may calculate expected code length correctly while failing to understand why prefix-free boundaries matter.
A third may understand the arithmetic yet confuse average bits per symbol with the length of every individual encoded message.
These students need different explanations.
In a carefully managed three-student Additional Mathematics tutorial, a tutor can inspect the equation, the integer condition and the interpretation separately.
The immutable Secondary 1 Mathematics small-group tutorial in Clementi illustrates why indices, ratios and careful mathematical language are foundations for more advanced applications.
Students already progressing independently may not need tuition. Additional support is most useful when it targets an identified recurring misconception.
Frequently asked questions
Why do logarithms appear in digital information?
Because n bits provide 2^n possible fixed-length strings, and logarithms recover the number of bits required to distinguish a specified number of possibilities.
How many bits are needed for one thousand distinct fixed-length labels?
Ten bits. Nine provide only 512 patterns, while ten provide 1024.
What is a prefix-free code?
It is a code in which no complete codeword is the initial segment of another codeword, allowing unambiguous sequential decoding under the known code.
Can variable-length coding use fewer bits on average?
Yes, when code lengths and the source distribution are favourable, although not every individual message becomes shorter.
What does Shannon entropy measure?
It is a probability-based average information quantity, measured in bits for base-two logarithms, under a specified source model.
Why cannot every file be compressed losslessly?
There are fewer binary strings shorter than n bits than there are n-bit strings. A one-to-one encoding cannot place all possible n-bit inputs into strictly shorter distinct outputs.
Is information theory examined directly in G3 Additional Mathematics?
No. The information theory examples are enrichment applications of the subject’s exponent and logarithm foundations.
The lasting reason to learn logarithms through information
Additional Mathematics teaches students how repeated binary choices create exponentially many possibilities.
A logarithm turns that growth relationship backwards to find how many choices are needed.
Probability introduces the idea that some outcomes are more predictable than others.
A prefix code can exploit those differences under suitable conditions.
Entropy gives a deeper mathematical account of average information.
And counting arguments reveal why universal lossless shortening is impossible.
These connections show that logarithms are not merely calculator operations used to solve for x.
They are a language for understanding scale, possibilities and the mathematical limits of representation.
For connected reading, explore Why Study Additional Mathematics | Understand Mathematical Growth in Computer Algorithms, Why Study Additional Mathematics | Make Sense of Negative and Fractional Indices, Why Study Additional Mathematics | Use Logarithms to Find How Long Growth Takes, and the eduKateSG Additional Mathematics project library.