Boolean Algebra Questions

Determine the values of A, B, C, and D that make the sum term  equal to zero.

A. A = 1, B = 0, C = 0, D = 0
B. A = 1, B = 0, C = 1, D = 0
C. A = 0, B = 1, C = 0, D = 0
D. A = 1, B = 0, C = 1, D = 1

Answer: B

Derive the Boolean expression for the logic circuit shown below:

A. B. C. D. Answer: A One of De Morgan's theorems states that . Simply stated, this means that logically there is no difference between: A. a NOR and an AND gate with inverted inputs B. a NAND and an OR gate with inverted inputs C. an AND and a NOR gate with inverted inputs D. a NOR and a NAND gate with inverted inputs Answer: A The systematic reduction of logic circuits is accomplished by: A. using Boolean algebra B. symbolic reduction C. TTL logic D. using a truth table Answer: A How many gates would be required to implement the following Boolean expression before simplification? XY + X(X + Z) + Y(X + Z) A. 1 B. 2 C. 4 D. 5 Answer: D

Binary Practice questions

Binary Addition

 Reminder: 1 + 1 = 10

Questions

1. 101 + 11 = 1000
2. 111 + 111 = 1110
3. 1010 + 1010 = 10100
4. 11101 + 1010 = 100111
5. 11111 + 11111 = 111110

Binary Subtraction

Reminder: 10 - 1 = 1

Questions

6. 110 - 10 = 100
7. 101 - 11 = 10
8. 1001 - 11 = 110
9. 1101 - 11 = 1010
10. 10001 - 100 = 1101

Binary Multiplication

Hint: very similar to decimal multiplication

Questions

11. 10 x 10 = 100
12. 100 x 11 = 1100
13. 101 x 10 = 1010
14. 1011 x 11 = 100001
15. 11011 x 101 = 10000111

Binary Division

Hint: very similar to decimal division

Questions

16. 100 / 10 = 10
17. 111 / 11 = 10 R1
18. 1010 / 100 = 10 R10
19. 1101 / 11 = 100 R1
20. 10111 / 10 = 1011 R1

Binary Revision 2

Binary

Binary numbers are similar to decimal numbers. In the same way as each decimal digit is worth 10 times more than the digit to the right of it, each binary digit is worth 2 times more than the digit to the right of it. Also, in the same way as there are 10 possibilities in decimal (0-9), there are 2 possibilities in binary (0 or 1). This is why decimal is known as "base-10", and binary is known as "base-2".

For example, the number "10" would be written as "1010" - 1 eight and 1 two.

8	4	2	1
1	0	1	0	(10)

The reason computers use binary (and not decimal, octal, or anything else) as their primary number system is because binary is digital - either electricity is flowing (binary 1), or electricity isn't flowing (binary 0).

Binary Negative

Two's Complement

11001001 can be interpreted as either 201 (using normal binary) or -55 (using two's complement). A question will tell you if it should be read using two's complement.

1. Firstly, write the number in binary. For example, 54 becomes 00110110 in 8-bit binary.
2. Then, invert the digits (i.e. 1s become 0s, and 0s become 1s), so 00110110 becomes 11001001.
3. Finally, add 1 - 11001001 + 00000001 = 11001010.

-128	64	32	16	8	4	2	1
1	1	0	0	1	0	1	0	(-54)

Sign and Magnitude

Sign and magnitude uses the first bit for the sign (positive - 0, or negative - 1), and the remaining 7 bits for the number. For example, 11001011 represents -75. The first "1" means it is negative, and the remaining 7 bits (1001011) represent 75.

+/-	64	32	16	8	4	2	1
1	1	0	0	1	0	1	1	(-75)

Binary Addition

Binary addition is far easier than decimal addition! This is because there are only 4 possible sums - 0 + 0 = 0, 0 + 1 = 1, 1 + 0 = 1, 1 + 1 = 0, carry 1 (or 10, decimal 2). For example:

	128	64	32	16	8	4	2	1
	0	0	1	0	1	0	1	0	(42)
+	0	1	1	0	0	1	1	0	(102)
Carry:	1	1		1	1	1
	1	0	0	1	0	0	0	0	(144)

In an exam you must show your working to show that you didn't just convert the numbers to decimal, and then convert the solution from decimal back to binary.

Binary Subtraction

Binary subtraction can be done in two ways - just like decimal subtraction. You can either do 5 - 3, or -3 + 5 (using twos compliment - not sign and magnitude). Unless a question tells you to use twos compliment, you can use whichever method you prefer.

Using twos compliment:

	-128	64	32	16	8	4	2	1
	1	1	0	0	1	0	0	0	(-56)
+	0	1	1	0	0	1	0	1	(101)
Carry:	1	1
	0	0	1	0	1	1	0	1	(45)

Using subtraction:

	128	64	32	16	8	4	2	1
	1	0	0	1	0	1	0	0	(148)
-	0	0	1	0	0	1	1	1	(39)
Carry:	0	1	1	0	1	1 0	1	1
	0	1	1	0	1	1	0	1	(109)

Boolean Algebra Questions

Question1

Using Boolean algebra techniques, simplify the expression X . Y + X (Y + Z) + Y (Y + Z)

Solution:

Given: X . Y + X (Y + Z) + Y (Y + Z).

Applying distributive property, we get

X . Y + X (Y + Z) + Y (Y + Z) = X . Y + X . Y + X . Z + Y . Y + Y . Z

We know B . B = B

= X . Y + X . Y + X . Z + Y + Y . Z

We know A . B + A . B = A . B

= X . Y + X . Z + Y + Y . Z

= X . Y + X . Z + Y  [We know (B + BC = B)]

= Y + XZ      
                               

Question 2: 

XY¯XY¯ (X¯X¯ + YY) (X¯X¯ + XX)

Solution:

Given: XY¯(X¯+Y)(X¯+X)XY¯(X¯+Y)(X¯+X)

= XY¯(X¯+Y)XY¯(X¯+Y)

= (X¯+Y¯)(X¯+Y)X¯+Y¯)(X¯+Y)

= X¯+Y.Y¯X¯+Y.Y¯

= X¯X¯

Question 3 

Simplify X+YX¯X+YX¯

Solution:

Given: XX + YX¯YX¯

By using DeMorgan’s law, AB¯AB¯ = A¯+B¯A¯+B¯

X+YX¯=X+(Y¯+X¯)X+YX¯=X+(Y¯+X¯)

= (X+X¯)+Y¯(X+X¯)+Y¯

= 1+Y¯

Operating Systems

An operating system (OS) is system software that manages computer hardware and software resources and provides common services for computer programs. All computer programs, excluding firmware, require an operating system to function.
Time-sharing operating systems schedule tasks for efficient use of the system and may also include accounting software for cost allocation of processor time, mass storage, printing, and other resources.
For hardware functions such as input and output and memory allocation, the operating system acts as an intermediary between programs and the computer hardware, although the application code is usually executed directly by the hardware and frequently makes system calls to an OS function or is interrupted by it. Operating systems are found on many devices that contain a computer – from cellular phones and video game consoles to web servers and supercomputers.

The dominant desktop operating system is Microsoft Windows with a market share of around 83.3%. macOS by Apple Inc. is in second place (11.2%), and Linux is in third position (1.55%)). In the mobile (smartphone and tablet combined) sector, according to third quarter 2016 data, Android by Google is dominant with 87.5 percent and a growth rate 10.3 percent per year, followed by iOS by Apple with 12.1 percent and a per year decrease in market share of 5.2 percent, while other operating systems amount to just 0.3 percent. Linux is dominant in the server and super-computing sectors. Other specialized classes of operating systems, such as embedded and real-time systems, exist for many applications.


Memory management is a form of resource management applied to computer memory. The essential requirement of memory management is to provide ways to dynamically allocate portions of memory to programs at their request, and free it for reuse when no longer needed. This is critical to any advanced computer system where more than a single process might be underway at any time.

Several methods have been devised that increase the effectiveness of memory management. Virtual memory systems separate the memory addresses used by a process from actual physical addresses, allowing separation of processes and increasing the size of the virtual address space beyond the available amount of RAM using paging or swapping to secondary storage. The quality of the virtual memory manager can have an extensive effect on overall system performance.

A virtual machine is an operating system that emulates dedicated hardware. The user has the same experience on the virtual machine as they do on a dedicated machine. This enables the user to choose which operating system they would like to use. It saves cost by reducing the need for separate hardware.

Interrupts, the role of interrupts and Interrupt Service Routines (ISR), role within the fetch-decode-execute cycle Interrupts are useful in computers because, rather than continually polling the inputs for changes, as soon as an event (e.g. a button being pressed) happens, the CPU interrupts what it is currently doing and takes a snapshot of all the registers in the CPU at that point in time so that it can return to that state when it has finished dealing with the interrupt. The process that happens as
a result of the interrupt is called the Interrupt Service Routine (ISR).

There are different types of operating system.

A distributed operating system (OS) is a collection of independent networked nodes. Each node may have its own hardware associated with it, and there will be some sort of system management software that brings all the interconnected systems together and co-ordinates individual and collaborative activity on the different nodes.
Embedded operating systems are those that have a dedicated function and are part of (or can be part of ) a larger device. They are generally lower power consumption, low cost and use a limited amount of hardware resources which means that they need to be interfaced with in a more bespoke manner than commonplace OS systems. An example of an embedded operating system
would be embedded Linux on the Raspberry Pi.
Multi-user operating systems allow many different users to take advantage of the computer’s resources simultaneously. Multi-user operating systems share processor time. Unix is an example of a multi-user OS. Multi-tasking operating systems are those that allow you to have many different tasks happening at once, and so this is our standard modern operating system. However, some tasks such as complex scientific/bank calculations can require much more processing power. In this case, supercomputers are used but because they cost a lot of money, instead of being single-user they
are designed as multi-user systems so that many users can send tasks to them and share the resources.
Real-time operating systems (RTOS) are supposed to run under predefined deadlines and so can be classed as time critical. For instance, on an aeroplane when the pilot wants something to happen, it should do so straight away. One very important thing to remember about RTOS systems is that “the right answer too late is wrong”, since calculations for movements of a robot, for example, that arrive too late may no longer be valid.

Translators

Translator software

This is software that allows new programs to be written and run on computers, by converting source code into machine code.

Assembler

An assembler translates assembly language into machine code. Assembly language consists of mnemonics for machine opcodes so assemblers perform a 1:1 translation from mnemonics to a direct instruction. For example:

LDA #4 converts to 0001001000100100

Conversely, one instruction in a high level language will translate to one or more instructions at machine level.

Advantages of using an Assembler:

Very fast in translating assembly language to machine code as 1 to 1 relationship
Assembly code is often very efficient (and therefore fast) because it is a low level language
Assembly code is fairly easy to understand due to the use of English-like mnemonics

Disadvantages of using Assembler:

Assembly language is written for a certain instruction set and/or processor
Assembly tends to be optimised for the hardware it's designed for, meaning it is often incompatible with different hardware
Lots of assembly code is needed to do relatively simple tasks, and complex programs require lots of programming time

Compiler

A Compiler is a computer program that translates code written in a high level language to a lower level language, object/machine code. The most common reason for translating source code is to create an executable program (converting from a high level language into machine language).

Advantages of using a compiler

Source code is not included, therefore compiled code is more secure than interpreted code
Tends to produce faster code than interpreting source code
Produces an executable file, and therefore the program can be run without need of the source code

Disadvantages of using a compiler

Object code needs to be produced before a final executable file, this can be a slow process
The source code must be 100% correct for the executable file to be produced

Interpreter

An interpreter program executes other programs directly, running through program code and executing it line-by-line. As it analyses every line, an interpreter is slower than running compiled code but it can take less time to interpret program code than to compile and then run it — this is very useful when prototyping and testing code. Interpreters are written for multiple platforms, this means code written once can be run immediately on different systems without having to recompile for each. Examples of this include flash based web programs that will run on your PC, MAC, games console and Mobile phone.

Advantages of using an Interpreter

Easier to debug(check errors) than a compiler
Easier to create multi-platform code, as each different platform would have an interpreter to run the same code
Useful for prototyping software and testing basic program logic

Disadvantages of using an Interpreter

Source code is required for the program to be executed, and this source code can be read making it insecure
Interpreters are generally slower than compiled programs due to the per-line translation method

Hardware and Software

Hardware is the physical and electrical components of the computer. It is the platform on which software executes.

Processor:
o   ‘Brain’ of the computer
o   Big finite state machine
Main memory:
o   Random Access Memory (RAM) – volatile because when the computer is switched off – the contents are lost, temporary memory.
o   Read only Memory (ROM) – non-volatile – the contents in the ROM is not lost when the computer is switched off.
EEPROM :
o   Electronic Erasable Programmable Read Only Memory
o   Can read and write to the memory and it is not lost when the computer is switched off.
o   Can write to it as well but it is a lot slower to write to it.
CPU:
o   Processor
o   Main memory
o   Computer Buses
An input/output device is a device that inputs or outputs data through its input or output controller.
An I/O device:
o   Has a set of status, data and command registers.
o   Electronics which allow data transfer between it and other components.
 Each main memory location has a main memory address so the processor knows which memory to address when it needs it to run a program.
 Stored program concept – a program must be stored in main memory for it to run because the program control unit in the processor needs to fetch the machine code instructions in sequence and execute them one at a time.
Processor:
o   Program Control Unit (PCU) – fetches machine code instructions from main memory and executes them one at a time.
o   Arithmetic and Logic Unit (ALU) – performs arithmetic and logical calculations.
o   Registers – fast memory locations which are used to carry out certain things – these are used instead of using main memory because it would take a lot longer for the processor to fetch everything from the main memory so it is faster.

Software consists of sequences of instructions called programs which can be understood and executed by the hardware.

System software: Controls the operation of the computer. It allows the user to perform tasks without knowing the complexities of the machine.

Operating system software
An operating system (OS) is a set of programs that manage computer hardware resources and provide common services for application software. The operating system is the most important type of system software in a computer system. Without an operating system, a user cannot run an application program on their computer (unless the application program is self booting).


The OS manages functions like Time slicing and other Time-sharing operations and schedule tasks for efficient use of the system and may also include accounting for cost allocation of processor time, mass storage, printing, and other resources.

For hardware functions such as input/output and main memory management, the operating system acts as a middleman between application programs and the computer hardware, although the application code is usually executed directly by the hardware it will frequently call the OS or be interrupted by it. Operating systems can be found on almost any device that contains a computer, from mobile phones and video game consoles to supercomputers and web servers.

Examples of popular modern operating systems include Android, iOS, Linux, Mac OS X and Microsoft Windows, but don't use these names in the exam!

Extension: Open vs Closed Source operating systems
You might hear the words Open Source when you read about operating systems. Linux is the most well known Open Source OS and Windows is the most well known Closed Source OS. So what does this mean?

Open Source programs are programs where you can see the code (the source), you can edit it, copy it and use as you wish within the confines of an open source license. You can even sell it, but the person would be welcome to acquire the code for free if they wanted. As a result of this Linux is not developed by one person or one company but uses code developed by thousands of people, working for different organisations all over the world. And as a result there are many different versions (known as distributions) of Linux out there including Ubuntu, Slackware and Fedora. Android is built using Linux code.

Closed Source software doesn't allow people to look at the code or adapt it. Companies normally sell closed source products and you'll have to pay for a copy of Windows. Currently about 83% of desktops run the Windows OS.

Utility programs

Utility software is a type of system software which has a very specific task to perform related to the working of the computer, for example anti virus software, disk defragment etc.

Utility software should not be confused with application software, which allows users to do things like creating text documents, playing games, listening to music or surfing the web. Rather than providing these kinds of user-oriented or output-oriented functionality, utility software usually focuses on how the computer infrastructure (including the computer hardware, operating system, application software and data storage) operates. Due to this focus, utilities are often rather technical and targeted at people with an advanced level of computer knowledge.

Examples of utility software include:

Virus scanner - to protect your system from trojans and viruses
Disk defragmenter - to speed up your hard disk
System monitor - to look at your current system resources
File managers - to add, delete, rename and move files and folders

Library programs

Library programs are collections of compiled routines which are shared by multiple programs, such as the printing function.


Library programs contain code and data that provide services to other programs such as interface (look and feel), printing, network code and even the graphic engines of computer games. If you have ever wondered why all Microsoft Office programs have the same look and feel, that is because they are using the same graphical user interface libraries. For computer games a developer might not have the time and budget to write a new graphics engine so they often buy graphical libraries to speed up development, this will allow them to quickly develop a good looking game that runs on the desired hardware. For example Battlefield 3 and Need for Speed both use the same Frostbite engine.

The Edge Triggered D Type Flip-flop

D Type Flip-flops

The major drawback of the SR flip-flop (i.e. its indeterminate output and non-allowed logic states) described in Digital Electronics Module 5.2 is overcome by the D type flip-flop. This flip-flop, shown in Fig. 5.3.1 together with its truth table and a typical schematic circuit symbol, may be called a Data flip-flop because of its ability to ‘latch’ and remember data, or a Delay flip-flop because latching and remembering data can be used to create a delay in the progress of that data through a circuit. To avoid the ambiguity in the title therefore, it is usually known simply as the D Type. The simplest form of D Type flip-flop is basically a high activated SR type with an additional inverter to ensure that the S and R inputs cannot both be high or both low at the same time. This simple modification prevents both the indeterminate and non-allowed states of the SR flip-flop. The S and R inputs are now replaced by a single D input, and all D type flip-flops have a clock input.

Edge Triggered D Type Flip-flop

The clock pulse applied to the flip-flop is reduced to a very narrow positive going clock pulse of only about 45ns duration, by using an AND gate and applying the clock pulse directly to input ‘a’ but delaying its arrival at input ‘b’ by passing it through 3 inverters. This inverts the pulse and also delays it by three propagation delays, (about 15ns per inverter gate for 74HC series gates). The AND gate therefore produces logic 1 at its output only for the 45ns when both ‘a’ and ‘b’ are at logic 1 after the rising edge of the clock pulse.

Boolean Algebra

Boolean Algebra is used to analyze and simplify the digital (logic) circuits. It uses only the binary numbers i.e. 0 and 1. It is also called as Binary Algebra or logical Algebra. Boolean algebra was invented by George Boole in 1854.

Boolean Laws
There are six types of Boolean Laws.

Commutative law
Any binary operation which satisfies the following expression is referred to as commutative operation.

Commutative Law
Commutative law states that changing the sequence of the variables does not have any effect on the output of a logic circuit.

Associative law
This law states that the order in which the logic operations are performed is irrelevant as their effect is the same.

Associative Law
Distributive law
Distributive law states the following condition.

Distributive Law
AND law
These laws use the AND operation. Therefore they are called as AND laws.

AND Law
OR law
These laws use the OR operation. Therefore they are called as OR laws.

OR Law
INVERSION law
This law uses the NOT operation. The inversion law states that double inversion of a variable results in the original variable itself.

Logic Gates

Digital systems are said to be constructed by using logic gates. These gates are the AND, OR, NOT, NAND, NOR, EXOR and EXNOR gates. The basic operations are described below with the aid of truth tables.

The XOR gate (sometimes EOR gate, or EXOR gate and pronounced as Exclusive OR gate) is a digital logic gate that implements an exclusive or; that is, a true output (1/HIGH) results if one, and only one, of the inputs to the gate is true. If both inputs are false (0/LOW) or both are true, a false output results.

January Mock Corrections

Paper1

1Bi) The system stores floating point numbers in normalised form using 2's complement with a 12-bit mantissa and a 4-bit exponent as follows.

Num1             A802                101010000000  0010            -2.75

Bii) Why should floating point numbers be stored in normalised form?

To maximize precision in a given number of bits to maximize the accuracy in a given number of bits, and to minimize rounding errors.


2B)  A normalised floating point representation uses an 8-bit mantissa and a 4-bit exponent, both stored using two's complement format.

1.0110000    0010
=-2.5


2C) write the normalised floating point representation of the denary value 12.75.
           0.1100110        0010

Q3E)  Run-length encoding (RLE) is an example of  compression method that could be used to reduce the amount of memory required to store the icon.
Describe the principle used by RLE to compress a file and explain why RLE is an appropriate compression method for compressing images such as icons.

Identify multiple data values/ colours that are the same and represents them as one data values. E.g b,b,b,b=4b. Icons contain sequences of pixels that are the same colour. RLE is a lossless compression so the quality will not be effected.

5B) If an image required 3000 colours - how many bits would be required for the colour depth and why?

12 bits is enough because it is the smallest number of bits that can accommodate 3000 colours. 12 bits can represent a max number of 4096 colours which is more than 3000.

Bubble Sort

The bubble sort is used to sort a list of numbers. It works by comparing pairs of numbers and swapping them if necessary. It means that after each iteration the next largest number in the sequence will go to the top.

Original=       1  2   7  4  5
1st Iteration= 1  2   4  5  7

You continue going through each iteration until no swaps are made. Then it is complete.

Pseudocode

Repeat
Swapped= false
For 1 to (array length) do
If A(i) > A(i + 1) then
temp=A(i)
swap(A(i)=A(i + 1))
A(i + 1) = temp
Swapped = true
End If
End for
until not swapped
End Procedure

VB Code

Module Module1

    Dim num(8) As Integer

    Dim swap As Boolean

    Dim Temp As Integer

    Sub Main()

        num(1) = 2

        num(2) = 1

        num(3) = 4

        num(4) = 8

        num(5) = 6

        num(6) = 5

        num(7) = 7

        num(8) = 3

        Do

            swap = False

            For index = 1 To 8 - 1

                If num(index) > num(index + 1) Then

                    Temp = num(index)

                    num(index) = num(index + 1)

                    num(index + 1) = Temp

                    swap = True

                End If

            Next

        Loop Until swap = False

        For index = 1 To 8

            Console.WriteLine(num(index))

        Next

        Console.ReadLine()

    End Sub

End Module