1 of 27

CSC-105

​

​

Introduction to Computer Science

Lecture 1.1.

2 of 27

Communication

  • Covid lockdown. No phone. No internet.
  • How do you communicate?

3 of 27

Communication

  • Covid lockdown. No phone. No internet.
  • How do you communicate?
  • What if you had flashlights?

4 of 27

Communication

  • How about drawing letters with the flashlight?

5 of 27

Communication

  • How about drawing letters with the flash lights?
  • Can you think of a better communication scheme?

6 of 27

Blinking lights?

  • Can we use quick on and offs of the flash light to communicate using blinking lights?

​

  • 1 blink = On + Off

Blink 1

Blink 2

7 of 27

Our first encoding scheme

  • Brief pause in blinking for spaces between letters

Letter

Blinks

A

1

B

2

C

3

D

4

..

..

..

..

Z

26

Blink 1

Blink 2

8 of 27

Efficiency

H 8

O 15

W 23

​

A 1

R 18

E 5

​

Y 25

O 15

U 21

​

------------

131 !

  • How many blinks for “How are you”?

Letter

Blinks

A

1

B

2

C

3

D

4

..

..

..

..

Z

26

9 of 27

Missing characters?

  • What about question mark?

​

    • and numbers
    • and punctuation

​

  • It already takes us 131 blinks to communicate short sentences. With more characters, it is only going to become less efficient

​

Letter

Blinks

A

1

B

2

C

3

D

4

..

..

..

..

Z

26

10 of 27

Improving Efficiency

  • How can we improve the efficiency of this communication scheme?

​

  • Are all letters equally common in English language?

​

  • Is ‘X’ as common as ‘A’?

​

Letter

Blinks

A

1

B

2

C

3

D

4

..

..

..

..

Z

26

11 of 27

Improving Efficiency

  • Are all letters equally common in English language?

Letter

Blinks

A

1

B

2

C

3

D

4

..

..

..

..

Z

26

Frequency Distribution

Sorted Alphabetically

12 of 27

Improving Efficiency

Frequency Distribution

Sorted By Frequency

  • What if we used fewer blinks for the more commonly used letters?

Letter

Blinks

E

1

T

2

A

3

O

4

..

..

..

..

Z

26

13 of 27

Improved Efficiency

​

Alphabetical order based Encoding

Frequency based Encoding

H

8

8

O

15

4

W

23

14

​

​

​

A

1

3

R

18

9

E

5

1

​

​

​

Y

25

18

O

15

4

U

21

13

Total blinks:

131

74

  • In our original encoding scheme, we needed 131 blinks to send message “How are you”

​

  • In our new frequency based encoding scheme, we need only 74 blinks to send the same message

​

  • We’ve improved our efficiency ~43% !

​

  • 74 blinks is still a lot...

​

  • How can we improve further?

14 of 27

Long blink

  • What if we added another type of blink: Long blink?

​

  • So then we’ll have two kinds of blinks: Short blink and Long blink?

Short blink:

Long blink:

15 of 27

Morse Code

  • What we’ve essentially done is re-created Morse code
  • Analogous to short blink and long blink, morse code has dots . and dashes _

16 of 27

Morse Code

17 of 27

Morse code

Short blink:

Long blink:

time

t1

t2

t3

t4

  • “Unit” here is a fixed unit of time,

say 1 second or 1 minute.

​

  • As long as a dash is always three times the duration of a dot and a dot is the same duration as a space, the exact value of time unit does not matter.

18 of 27

Improved Efficiency

​

Alphabetical order based Encoding

Frequency based Encoding

Morse Code

H

8

8

4

O

15

4

3

W

23

14

3

​

​

​

​

A

1

3

2

R

18

9

3

E

5

1

1

​

​

​

​

Y

25

18

4

O

15

4

3

U

21

13

3

Total blinks:

131

74

26

19 of 27

Improved Efficiency

​

Alphabetical order based Encoding

Frequency based Encoding

Morse Code

H

8

8

4

O

15

4

3

W

23

14

3

​

​

​

​

A

1

3

2

R

18

9

3

E

5

1

1

​

​

​

​

Y

25

18

4

O

15

4

3

U

21

13

3

Total blinks:

131

74

26

  • In our original encoding scheme, we needed 131 blinks to send message “How are you”

​

  • In the frequency based encoding scheme, we needed 74 blinks to send the same message

​

  • In Morse code, we need only 26 blinks!

​

  • 80% improvement over original scheme!

​

  • 65% improvement over second scheme!

​

20 of 27

Decoding Morse Code

  • Morse code is easy to send but hard to receive

​

  • The problem is we have a mapping:
    • English alphabet → Dots and Dashes

​

  • But not the reverse mapping:
    • Dots and Dashes → English alphabet

​

21 of 27

Decoding Morse Code

  • Let’s try to create the reverse mapping:
    • Dots and Dashes → English alphabet

​

​

  • How do we sort it?
    • How about the length of dots and dashes?

​

22 of 27

Decoding Morse Code

.

E

_

T

..

I

._

A

_.

N

_ _

M

...

S

.._

U

._.

R

._ _

W

_..

D

_._

K

_ _ .

G

_ _ _

O

....

H

..._

V

.._.

F

.._ _

Ȗ

._..

L

._._

A

._ _ .

P

._ _ _

J

....

B

..._

X

.._.

C

.._ _

Y

._..

Z

._._

Q

._ _ .

Ö

._ _ _

ş

length=1

length=2

length=3

length=4

  • Do you see a pattern here?

23 of 27

Decoding Morse Code

.

E

_

T

..

I

._

A

_.

N

_ _

M

...

S

.._

U

._.

R

._ _

W

_..

D

_._

K

_ _ .

G

_ _ _

O

....

H

..._

V

.._.

F

.._ _

Ȗ

._..

L

._._

A

._ _ .

P

._ _ _

J

....

B

..._

X

.._.

C

.._ _

Y

._..

Z

._._

Q

._ _ .

Ö

._ _ _

ş

length=1

length=2

length=3

length=4

  • The table for each length has twice the size as the table for length-1

24 of 27

Decoding Morse Code

  • The table for each length has twice the size as the table for length-1

​

  • The first table has 2 codes, the second has 2✕2, the third has 2✕2✕2 and the fourth has 2✕2✕2✕2

​

  • How can we come up with a general formula for this?

Length (number of dots and dashes)

Rows (number of english letters)

1

2

2

4

3

8

4

16

25 of 27

Decoding Morse Code

Length (number of dots and dashes)

Rows (number of english letters)

1

21

2

22

3

23

4

24

  • This means n dots and dashes can encode 2n english letters

​

    • In trying to decode Morse code, we have gained an insight into the encoding.

​

  • Why is it 2 in the base? What is so special about 2 in Morse code?

26 of 27

For next time

  • Next time, we’ll see how we can use the insight towards better decoding of Morse code

​

​

  • Also on the agenda for next week, circuits!

27 of 27

Decoding Morse Code

  • To make the process of making decoding Morse code easier, you might want to draw something like this big tree-like diagram on the right

​

  • The diagram shows the letters that result from each particular consecutive sequence of dots and dashes

​

  • To decode a particular sequence, follow the arrows from left to right

​

  • For example, following arrows from the root of the tree on the left ends at R