EST2501 Digital Fundamentals (1): Digital Fundamentals

Posted on Edited on In Word count in article: 3.4k Reading time ≈ 12 mins.

Digital Electronics is a fundamental course for electronics and computer engineering. The course, Digital Electronics with course code EST2501, is offered by SAIS at SJTU to grade 1 SEIEE students, accounting for 2 credits. Although either a CS or IE undergraduate at SJTU should take this course, I think you can grasp a better understanding of this course if you have some background in discrete mathematics and computer architecture, especially for contents related to number systems and signed numbers. In the other hand, such contents like flip-flops serve as an important role in memory, which is a main focus in architecture course.

Textbook for this course is Digital Fundamentals by Thomas L. Floyd, which is a widely used textbook for these courses. It is really a detailed textbook with precise illustrations and clear explanations. However, it is also quite lengthy and too detailed - learning with reading every page exactly as it is written is a little inefficient. Therefore, I recommend to read the textbook in a more flexible way: just skimming through examples, too detailed descriptions and explanations, and focus on the main concepts and principles.

However, this course does not contain all chapters of this textbook, and only chapter 1 - 9 are included in the syllabus. These chapters are summarized into four parts, corresponding to the four articles in this series of notes. The first two parts, Digital Fundamentals and Logical Fundamentals, introduce the basic concepts and principles of digital electronics, while the last two parts, Combinational Logic Circuit and Sequential Logic Circuit, focus on the design and analysis of digital circuits.

Collections of EST2501 Digital Electronics notes:

  1. Digital Fundamentals (this article);
  2. Logical Fundamentals;
  3. Combinational Logic Circuit;
  4. Sequential Logic Circuit.

You can find a general introduction to this course in the first article of this series.

Digital and Analog Quantities

  • Analog signal is continuous in both time and amplitude.
  • Sampled signal is continuous in amplitude but discrete in time.
  • Quantized signal is discrete in both time and amplitude.

Binary Digits, Logical Levels and Digital Waveforms

In digital electronics, there are only two possible states represented by different voltage levels: HIGH (true, 1) and LOW (false, 0).

In some active-LOW systems, the HIGH and LOW levels are reversed, where HIGH represents false (0) and LOW represents true (1). However, in most cases and this course we will only focus on the active-HIGH systems.

Logical Levels and Threshold Voltage

Ideally there should be only one voltage level for HIGH and one voltage level for LOW, but in practice there is always some noise and variation in the voltage levels. Therefore, in an actual digital circuit, a HIGH or LOW signal is defined as any voltage level that is above or below a certain threshold voltage, respectively. This allows for some tolerance in the voltage levels and ensures that the circuit can operate reliably even in the presence of noise.

In the picture beloew, and are the minimum and maximum voltage levels that can be considered as LOW, while and are the minimum and maximum voltage levels that can be considered as HIGH. The region between and is considered unacceptable because it may not be reliably interpreted as either HIGH or LOW.

VL(min)VL(max)VH(min)VH(max)LOW(binary0)UnacceptableHIGH(binary1)

Digital Waveform

Digital waveforms consist of voltage levels that are changing back and forth between the HIGH and LOW levels or states.

Ideal Waveform

The figure below shows an ideal digital positive-going waveform. In ideal waveform, the edge from LOW to HIGH is called a rising edge, while the edge from HIGH to LOW is called a falling edge.

LOWHIGHt0t1RisingorleadingedgeFallingortrailingedge

Real Waveform

In ideal waveform, the rising and falling edges are assumed to change in zero time. However, in real waveform, the edges are not vertical but sloped, and the time it takes for the signal to change from 10% LOW to 90% HIGH or from HIGH to LOW is called the rise time or fall time, respectively. The time during which the pulse is over 50% of the amplitude is called the pulse width.

AmplitudeBaseline10%50%90%trRisetimetfFalltimetwPulsewidthOvershootRingingDroopUndershootRinging

Duty Cycle and Frequency

A periodic pulse is a pulse that repeats itself at regular intervals. The time between the start of one pulse and the start of the next pulse is called the period, usually denoted as . The number of pulses per second is called the frequency, usually denoted as , and is related to the period by .

Duty cycle is the ratio of the pulse width to the period, usually expressed as a percentage as where is the pulse width.

The clock signal is a special periodic pulse that is used to synchronize the operations of a digital circuit. The clock waveform itself does not contain any information.

Data Transfer

When bits are transferred in serial communication, they are sent one at a time over a single wire or channel.

SendingdeviceReceivingdevice10110010t0t1t2t3t4t5t6t7

In parallel communication, multiple bits are sent simultaneously over multiple wires or channels.

SendingdeviceReceivingdevicet0t110110010

Digital Integrated Circuits

For a integrated circuit (IC), the pin 1 is usually marked with a dot or a notch. The pins are numbered in a counterclockwise direction when viewed from the top. The pin 1 is usually used as a reference point for identifying the other pins and their functions.

12345678910111213141516Pin1identi¯erNotch489131418319Pin1identi¯er

Number Systems

Number system. Mostly used number systems in digital electronics are decimal (10), binary (2), octal (8), and hexadecimal (16).

Sum-of-weight expression. Under -base number system, the value of a number can be calculated as where is the digit at position and is the base of the number system. This expression can be used to convert a number from one base to another, especially to decimal.

Conversions

Conversion between decimal and -base number system

For integer decimal number convention to -base number system, repeated division by r is used, and by recording the remainders in reverse order we can get the digit of the number.

1
2
3
4
5
6
2 | 45 ... 1
  2 | 22 ... 0
    2 | 11 ... 1
      2 | 5  ... 1
        2 | 2  ... 0
          2 | 1  ... 1

Take the above example for converting 45 to binary. We can see that the remainders are 1, 0, 1, 0, 1, 1 from bottom to top. So the binary representation of 45 is .

For fractional decimal number convention to -base number system, repeated multiplication by r is used, and by recording the integer part of the result we can get the digit of the number.

1
2
3
0.625 * 2 = 1.25 ... 1
0.25  * 2 = 0.5  ... 0
0.5   * 2 = 1.0  ... 1

Take the above example for converting 0.625 to binary. We can see that the integer parts are 1, 0, 1 from top to bottom. So the binary representation of 0.625 is .

Conversion between binary, octal and hexadecimal

Since and , we can convert between binary and octal or hexadecimal by grouping the binary digits into groups of 3 or 4 respectively. Vice versa, we can convert octal or hexadecimal to binary by replacing each digit with its 3 or 4 bit binary equivalent.

The grouping should be done from the right for integer part and from the left for fractional part, i.e., from most significant bit (MSB) to least significant bit (LSB). If the number of digits is not a multiple of 3 or 4, we can add leading zeros for integer part or trailing zeros for fractional part to make it a multiple.

1
2
3
Binary          101101
Octal           010 101 55
Hexadecimal     00101101    2D

Take 45 as an example. In other words, hexidecimal and octal number system are just zipped version of binary number system.

Binary Operations

Binary Addition

Binary addition follows the same rules as decimal addition, but with only two digits (0 and 1). The rules are: | A | B | Sum | Carry Out | |—|—|—–|———–| | 0 | 0 | 0 | 0 | | 0 | 1 | 1 | 0 | | 1 | 0 | 1 | 0 | | 1 | 1 | 0 | 1 |

Binary Subtraction

Rules for binary subtraction are: | A | B | Difference | Borrow Out | |—|—|————|————| | 0 | 0 | 0 | 0 | | 0 | 1 | 1 | 1 | | 1 | 0 | 1 | 0 | | 1 | 1 | 0 | 0 |

Binary Multiplication

Binary multiplication is similar to decimal multiplication, but with only two digits (0 and 1). The rules are: | A | B | Product | |—|—|———| | 0 | 0 | 0 | | 0 | 1 | 0 | | 1 | 0 | 0 | | 1 | 1 | 1 |

For multiplying two binary numbers, we can use the shift and add method. We multiply each bit of the second number (multiplier) with the first number (multiplicand) and shift the result to the left according to the position of the bit. Finally, we add all the shifted results together to get the final product.

Signed Numbers

Sign bit and signed magnitude. In signed binary numbers, the (MSB) is used as the sign bit. If the sign bit is 0, the number is positive; if the sign bit is 1, the number is negative. This number system is called signed magnitude, where positive and negative numbers with same absolute value have the same magnitude but different signs.

1’s complement. In one’s complement representation, negative numbers are represented by inverting all the bits of the corresponding positive number except the sign bit. For example, if we have a 4-bit system, the number 5 is represented as 0101, and its one’s complement (which represents -5) is 1010.

2’s complement. In two’s complement representation, negative numbers are represented by taking the one’s complement of the corresponding positive number and adding 1 to it. For example, if we have a 4-bit system, the number 5 is represented as 0101, and its two’s complement (which represents -5) is 1011.

Arithmetic Operations with Signed Numbers

Addition. Using 2’s complement, we can perform addition of signed numbers by simply adding the two numbers together. If the result exceeds the range of representable numbers, we can ignore the carry out from the MSB.

Subtraction. Basically, subtraction changes the sign of the subtrahend and then performs addition. Result of subtraction is called difference. To subtract two signed numbers, we can take the 2’s complement of the subtrahend and add it to the minuend and discard the carry out from the MSB if it exists.

Multiplication. To multiply two signed numbers, take the absolute values of the numbers, perform multiplication as if they were unsigned, and then determine the sign of the result based on the signs of the original numbers. If the signs of the original numbers are different, the result is negative; otherwise, it is positive.

Booth algorithm can be considered. See computer architecture textbooks for more details.

Division. Take the absolute values of the numbers, do several times of subtraction as if they were unsigned, and then determine the sign of the result based on the signs of the original numbers.

Codes

Binary Coded Decimal (BCD)

Binary Code Decimal (BCD) is a way to represent decimal digits with binary code. Each decimal digit (0-9) is represented by a 4-bit binary code. Most ways of representing BCD are named with the weight of the bits, such as 8421, 2421, 5421, etc.

The most commonly used BCD code is the 8421 code, where the weights of the bits are 8, 4, 2, and 1 from left to right. Therefore, 8421 code of each digit is actually the binary representation of that digit.

It is worth noting that BCD codes have some invalid combinations, such as 1111 in 8421 code.

Gray Code

Gray code is the most used digital code in digital electronics. It is a binary code where two successive values differ in only one bit. This property makes it useful for error correction and for reducing the chances of errors during data transmission.

To convert a binary number to its corresponding Gray code, we can use the following steps: 1. The most significant bit (MSB) of the Gray code is the same as the MSB of the binary number. 2. For each subsequent bit of the Gray code, we can calculate it by performing an exclusive OR (XOR) operation between the current bit of the binary number and the previous bit of the binary number.

1
2
3
Binary: 1 -+> 0 -+> 1 -+> 1 -+> 0
        |     |     |     |     |
Gray:   1     1     1     0     1

To convert a Gray code back to its corresponding binary number, we can use the following steps: 1. The most significant bit (MSB) of the binary number is the same as the MSB of the Gray code. 2. For each subsequent bit of the binary number, we can calculate it by performing an exclusive OR (XOR) operation between the current bit of the Gray code and the previous bit of the binary number.

1
2
3
Gray:   1   / 1   / 0   / 1   / 1
        |  +  |  +  |  +  |  +  |
Binary: 1 /   0 /   0 /   1 /   0

Error Codes

Parity bit is a simple error detection code that adds an extra bit to a binary number to indicate whether the number of 1s in the binary number is even or odd. There are two types of parity bits: even parity and odd parity, counting for the number of 1s.

In even parity checking, the parity bit is set to 1 if the number of 1s in the binary number is even, and set to 0 if the number of 1s is odd. Odd parity can be defined vice versa.

CRC code and Hamming code can be considered. See computer architecture textbooks for more details.