1.4 Data Types and Structures Flashcards
What is a data type?
Formal classification of the type of data being stored or manipulated within a program to determine which operations can be performed on that data
What are primitive data types?
Common data types built into the language which can only contain one value
What are some examples of data types?
Integer
Float/real
Boolean
Char
String
What is an integer?
A positive or negative whole number
What is an example of an integer?
1
-98
38420
What is float/real?
A positive or negative number which can include decimal points
What is an example of a float/real?
1.849
-45.3
What is a Boolean?
Only one of True or False
What is an example of a Boolean?
True
False
What is a char?
A single character
What is an example of a char?
“a”
”#”
“5”
What is a string?
Not a primitive data type but a basic one in most languages
Collection of char data types
What is an example of a string?
“hello!”
“sh63£”
What is a composite/compound data type?
Built by combining primitive data types
What is an example of a composite/compound data type?
Record
Class
What is a data structure?
Collection of data organised to allow efficient processing
Lend themselves to different applications
Some highly specialised to specific tasks
What is an abstract data type?
Conceptual model
Describes how data is organised and which operations can be carried out on data
From perspective of end-user who doesn’t need to know how it’s implemented
What is binary?
Base 2
Uses 1s and 0s
List the forms of storage (e.g. bit, byte) from smallest to largest
Bit
Nibble
Byte
Kilobyte
Megabyte
Gigabyte
Terabyte
Petabyte
What is a bit?
A single 1 or 0
Smallest form of data storage in a computer
What is a nibble?
4 bits
What is a byte?
8 bits
2 nibbles
What is a kilobyte?
1000 bytes
What is a megabyte?
1000 KB
What is a gigabyte?
1000 MB
What is a petabyte?
1000 TB
What is a terabyte?
1000 GB
What is the largest number that can be stored by a nibble?
15
What is the largest number that can be stored by a byte?
255
What is 9 as a byte?
00001001
What is 102 as a byte?
01110011
What is hexadecimal?
Base-16
0-9 and A-F
What is each hex digit equivalent to?
A nibble
What are the uses of hex?
RBG = representing colours
MAC addresses
Memory dumps
What are the advantages of hex?
Easier to read and interpret
Fewer digits to represent the same value
Compared to binary, less likely that digit written down incorrectly
How do you convert denary to hex?
Convert into binary
Split into nibbles
Convert each nibble to hex
What is 87 in hex?
87 = 01010111 = 57
What is 210 in hex?
210 = 11010010 = D2
How do you convert hex to denary?
Convert all terms to denary (as per a nibble)
Times those numbers by 16 to the power of the nibble they are in minus 1 (if it’s the second nibble, times by 16^1)
Add numbers together
What is B9 in denary?
B9 = 176 + 9 = 185
What is 2CA in denary?
2CA = 512 + 192 + 10 = 718
What are two ways of representing negative numbers in binary?
Sign and magnitude
Two’s complement
What is sign and magnitude?
Changing left most bit (most significant bit) to represent if negative or not
0 = positive
1 = negative
What is -10 in sign and magnitude?
10001010
What is 103 in sign and magnitude?
01100111
What is two’s complement?
Changing left most bit (most significant bit) to present either 0 or -128
1 = -128
0 = 0
What is the method for converting a number to two’s complement?
Calculate number as positive binary value
Keep rightmost 1 and everything to the right of it the same
Flip all other value
What is -103 in two’s complement?
103 = 01100111
-103 = 10011001
What are the rules for binary addition?
1 + 0 = 1
1 + 1 = 0 carry 1
0 + 0 = 0
1 + 1 + 1 = 1 carry 1
What is 99 + 103 in binary?
99 = 01100011
103 = 01100111
01100011 \+ 01100111 ------------------- 11001010 ------------------- 11 111
= 11001010
What is the method for binary subtraction?
Convert numbers to two’s complement
Flip number you’re subtracting to a negative
Add numbers together
What is 75 - 36 in binary?
75 = 01001011
36 = 00100100
-36 = 11011100
01001011
+ 11011100
——————
100100111
——————-
1 11
= 00100111
What is fixed point binary?
Decimal point doesn’t move
Values before fixed point represent whole numbers
Values after fixed point represent fractions
Can be expressed using Two’s complement
What is the problem with fixed point binary?
Underflow - when number is too small to be represented
What is 5.75 in fixed point binary?
0101.1100
What is floating point binary?
Decimal place can be moved
Enables greater range of numbers and greater precision of numbers
More efficient way of storing binary numbers
What values are needed in floating point binary?
Mantissa
Exponent
What is the exponent?
Where the decimal point should move to
What is the mantissa?
Number being represented
Where does the binary point start?
Between the two leftmost bits
Which way should be binary point move in the exponent is positive?
Right
Which way should the binary point move if the exponent is negative?
Left
What should the bits be filled with when the exponent is negative?
If first number is 1, fill with 1s
If first number is 0, fill with 0s
What does normalised mean?
Standard form that should be used to represent numbers
Using normalisation, make sure digit after the binary point is SIGNIFICANT
What should normalised positive numbers start with?
01
What should normalised negative numbers start with?
10
What is overflow?
Where the number is too large a positive or negative to store
Crashes
What is underflow?
When the number is too small to be able to store
Crashes
What is the method of adding normalised form numbers?
Check if exponents are the same. If not, increase smaller exponent to match higher one
When doing this, need to adjust floating point on mantissa to the left, the number of places that you need to increase the exponent by
Add together just the mantissas using normal binary addition rules
What is the method of subtracting normalised form numbers?
Check if exponents are the same. If not, increase smaller exponent to match higher one
When doing this, need to adjust floating point on mantissa to the left, the number of places that you need to increase the exponent by
Negate the value to subtract
Add together just the mantissas using normal binary addition rules
What is a character set?
Standard collection of characters and the bit patterns used to represent them to allow computers to be able to communicate and exchange text efficiently
What does ASCII stand for?
American Standard Code for Information Interchange
What is ASCII?
Each character encoded with binary string of 7 bits
What is the 8th bit in ASCII often reserved for?
Error-checking/correction purposes
What is Unicode?
Uses more bits to store a character than ASCII, meaning a wider range of characters can be stored
What are the advantages of Unicode?
Can support languages with alphabet character sets larger than 26
Uses up to 32 bits to represent each character and can be used to represent special symbols
Supports over 4 billion possible codes
What version of ASCII is generally used?
UTF-16
What is bitwise manipulation?
Allows the programmer to work with sets of bits through logical bitwise operations
In both high and low level languages, used to perform a logical operation on each individual bit of a binary number
What are logical bitwise operations?
Directly supported by the processor, making them fast and efficient
Works on a single bit (or set of bits) within a binary string
Often used in low-level languages to manipulate the contents of registers or memory locations
What are the four logical bitwise operations?
AND
OR
XOR
NOT
What are binary or logical shifts?
Used to move binary digits
Can be used for arithmetic operations
What is a mask?
Bit pattern that’s been defined by a programmer, allowing specific bits in a piece of data to be tested or altered
Binary string used in conjunction with a logical bitwise operator to identify or manipulate a single bit (set of bits) within another binary string
What does the AND logical bitwise operation do?
Turn off/select bits
What is the result of AND operator applied to the binary string 10111100 using a mask of 11110000?
10110000
What does the OR logical bitwise operation do?
Turn on/select bits
What is the result of OR operator applied to the binary string 10111100 using a mask of 11110000?
11111100
What does the XOR logical bitwise operation do?
Reverse/toggle/complement/inverse
What is the result of XOR operator applied to the binary string 10111100 using a mask of 11110000?
01001100
What does applying shifts do?
Divide or multiply binary values
What are the uses of shifts?
Multiplying and dividing by a factor of 2
Encryption/decryption
Data collision detection in a network
Compression algorithms
Routing packets of data
Peripheral communication protocols
Graphics manipulation
How is a logical left shift completed?
- moving all the bits of the number one place to the left
- discarding the most significant bit
- putting a 0 into the empty place on the right
How is a logical right shift completed?
- moving all bits of the number one place to the right
- discarding the least significant bit
- putting a 0 into the empty place on the left
Can you logically shift signed numbers?
No
What type of shift should be used if the number is signed?
Arithmetic shift
What is a arithmetic shift?
Most significant bit is not shifted
Remaining bits are shifted
Sign of number is preserved and empty places are padded
What happens in an arithmetic left shift of a positive number?
Empty places are padded with 0
What happens in an arithmetic left shift of a negative number?
Empty places are padded with 0
What happens in an arithmetic right shift of a positive number?
Empty spaces are padded with 0
What happens in an arithmetic right shift of a negative number?
Empty places are padded with 1
What is a circular/cyclic shift?
No bits are lost
Bits are shifted out at one end into the other end of register
What are the uses of a cyclic shift?
In cryptography, cyclic shift of a code will always yield another code (Twofish cipher makes extensive use of cyclic shift because they are very fast operations)
Cyclic left shift used in some operations in modular arithmetic
How do you multiply 12 x 6 using shifts and addition?
12 x 6 = (12 x 4) + (12 x 2)
What is a tuple?
Ordered sequence of elements stored under a single identifier
Data is immutable
What does immutable mean?
Cannot be changed
What are the uses of a tuple?
Returning multiple items from a function
Passing multiple values to a subroutine but grouped under a single parameter
Often used when returning records from a database
What is used to define a tuple?
()
What is used to access a tuple?
[]
What is an array?
Static data structure
Can only store data of the same data type
What does static mean?
Length doesn’t change during run time
How is an array defined?
[]
What is a 2D array?
Lets you use the equivalent of rows and columns
Each element in an array becomes a separate array
Each coordinate needs two values
How is a 2D array accessed?
name[x,y]
name[x][y]
What is a stack?
Abstract data type
LIFO
Static (if implemented using an array) but can be dynamic if implemented using other data structures (linked list)
What does LIFO stand for?
Last In First Out
What does LIFO mean?
Data is placed on top and removed from the top
What are the operations that can be performed on a stack?
push(data)
pop()
peek()
is_empty()
is_full()
What does push(data) do?
Adds an element to the top of the stack
What does pop() do?
Removes an element from the top of the stack and returns it
What does peek() do?
Returns a copy of the element on the top of the stack without removing it
What does is_empty do in a stack?
Checks whether a stack is empty
What does is_full do in a stack?
Checks whether a stack is at maximum when stored in a static structure
What are the uses of a stack?
Holds return addresses when subroutines are called (recursion)
Undo in word
Back button in web browser
In calculations to ensure correct order of precedence
When dealing with interrupts (current process and values put on stack to allow ISRs to be completed)
What is stack overflow?
Attempting to push onto a stack that’s full
What is stack underflow?
Attempting to pop from a stack that’s empty
How is a stack implemented?
Only need a single pointer to the top of the stack
Store maxSize of stack in variable to determine if stack full
Use top pointer or equivalent to keep track of top of stack
If stack empty, top = -1
What is a a queue?
Abstract data type
FIFO
Static (if implemented using an array) but can be dynamic if implemented using other data structures (linked list)
What does FIFO stand for?
First In First Out
What does FIFO mean?
Data is placed at the rear/back of the queue and removed from the front
What are the operations that can be performed on a queue?
enqueue(data)
dequeue()
is_empty()
is_full()
What does enqueue(data) do?
Adds an element to the back of the queue
What does dequeue() do?
Removes an element form the front of the queue and returns it
What does is_empty do in a queue?
Checks whether the queue is empty
What does is_full do in a queue?
Checks whether a queue is at maximum capacity (if size of queue is constrained)
What are the uses of a queue?
Simulation
Print queue
Priority queue (each element in queue has a priority and are ordered by priority?
How is a queue implemented?
Two pointers needed
Front pointer points to first item, initialised at 0
Rear pointer to last item, initialised at -1
Queue is empty when rear < front
What is a circular queue?
Reuses the empty slots at the front of the array that are caused when elements are dequeued
As items enqueued and rear pointer reaches last position of the array, wraps around to start of array (as long as not full)
As items dequeued, front points wraps around until passed rear pointer (meaning queue is empty)
How are the front and rear pointers moved in a circular queue?
rear = (rear + 1) % maxSize
front = (front + 1) % maxSize
What is a record?
Data structures consisting of a fixed number of variables (FIELDS)
What are fields in a record?
Each field has an IDENTIFIER and a data type
Each field can have a DIFFERENT DATA TYPE
How are fields retrieved from records?
nameOfRecord.fieldname
What is a linked list?
Abstract data type
DYNAMIC data structure used to hold a sequence
Other data types can be implemented using a linked list (stacks, queues)
Items in the sequence are in NON-CONTIGUOUS DATA LOCATIONS
Composed of nodes
Items stored in an order
What does dynamic mean?
Size of the list can change during runtime
What are the parts of a node?
The data (may be complex data structure)
A pointer (index) of the next node
What are the pointers of a linked list?
Start pointer (identifying first node in the list)
nextFree pointer (showing index of next free space in the array)
How is a linked list traversed?
- follow the start pointer to the first node. Examine data of this node
- if pointer of that node is not Null, follow pointer to next node
- repeat until end of list is reached (pointer of current node is Null)
What is the code for traversing a linked list (implemented using an array)?
cp = start
while cp != None:
print(list[cp][0])
cp = list[cp][1]
How is an item added to a linked list?
- start by checking if linked list is already full
- check if adding into an empty list
- checking if adding into the start of a list
What are the benefits of a linked list?
Data can be easily added or removed in an order without needing to move lots of other data items
Can be used to implement more abstract data types (queues, stacks, binary trees)
What are the problems of a linked list?
Traversal of a linked list is very slow
What is a doubly linked list?
Contains pointers to the next node and the previous node
What is a graph?
Abstract data type
Used to represent complex, non-linear relationships between objects
Consists of nodes (vertices) connected by edges (or arcs)
What are neighbours in graphs?
When graphs are connected by an edge
What is the degree of a node?
Number of nodes that it’s connected to
What is a loop in a graph?
An edge that connects a node to itself
What is a path in a graph?
Sequence of nodes connected by edges
What is a cycle in a graph?
Closed path
Path that starts and ends at the same node with no node visited more than once
What can graphs represent?
Social networking - nodes are individual people and edges represent that two people are acquaintances
Transport networks - nodes are towns and edges trainlines connecting two towns
Internet - nodes are routers and edges represent that two routers are connected
World Wide Web - nodes are webpages and edges represent that two pages are linked
What is an undirected graph?
Edges don’t have arrows so the graph can be traversed in both directions
What is a directed graphs?
Edges have arrows denoting direction of graph traversal
Edges don’t have arrows going both ways, they have two arrows if bidirectional
What is an unweighted graphs?
The edges don’t have values associated with them
What is a weighted graphs?
Edges have a value associated with them
Values could represent distance between places, time taken to travel, amount of network traffic
What is an adjacency matrix?
Each row and column represents a node
The item at [row, column] indicates a connection
Unweighted graphs have a 1 at each edge
What are the advantages of using an adjacency matrix to represent a graph?
Convenient to work with
Adding an edge is simple
What are the disadvantages of using an adjacency matrix to represent a graph?
Spare graph with not many connections (edges) will leave most cells empty, wasting a lot of memory space
What is an adjacency list?
List of nodes created and each node points to a list of adjacent nodes
Weighted graph represented as a dictionary of dictionaries
What does traversing mean?
Visiting all the nodes
What are the two types of graph traversal?
Depth first traversal
Breadth first traversal
What data structure does a depth first traversal use?
Stack
What is a depth first traversal suitable for?
Solutions where the answer is far from the node
Decision-based tree system
What is the method of a depth first traversal?
- push first node onto the stack and mark this node as visited
- repeat the following until stack is emptya. visit next unvisited node
b. push onto stack and mark as visited
c. if no further unvisited connected nodes, pop from stack
What data structure does a breadth first traversal use?
Queue
What is a breadth first traversal suitable for?
Answer is closer to the node
What is the method of a breadth first traversal?
- push first node onto queue and mark as visited
- repeat the following until all connected nodes to current node are marked as visiteda. visit next unvisited node
b. push onto queue and mark as visited - repeat following until queue is emptya. pop node from queue
b. repeated following until all connected nodes to the current node are marked as visitedi. visit next unvisited node ii. push onto queue and mark visited
What is a tree?
Common abstract data type - should not be used as generalised abstract data structure
Connected, undirected graph with no cycles which is used for searching
Ideally, BUILD ONCE, TRAVERSE OFTEN
What are the different types of tree?
Binary trees
Binary search trees
Expression trees
What is a root in a tree?
Start node for traversals
If tree has a root, called a rooted tree
What is a branch in a tree?
Path from the root to an end point
What is a leaf in a tree?
End point
What is the height of a tree?
Equal to the number of edges that connect root node to leaf node furthest from it
What is a rooted tree?
Tree with one node designated the root
Root commonly situated in diagrams above other nodes
Nodes connected by parent-child relationships
Node can have any number of children
What is a parent node?
Node that comes directly before another adjacent node (considered the child)
What is a binary tree?
Rooted trees
Each node has a max of 2 child nodes
Where is a binary tree used?
In compilers to build syntax trees
Within routers to store routing tables
What was a binary search tree built for?
To speed up searching
What is a binary search tree?
Nodes ordered to optimise searching
Rooted tree
Nodes of left subtree have values lower than root
Nodes of right subtree have values higher than root
What are the different parts of a node?
The data (may be primitive or more complex object)
Left pointer to a child
Right pointer to a child
What are the types of traversal of binary trees?
Pre-order
In-order
Post-order
Which type of traversal should be done in exams when asked for a depth first traversal?
Post order
What is a pre-order traversal?
Visit root, traverse left subtree, traverse right subtree
What is an in-order traversal?
Traverse left subtree, visit root, traverse right subtree
What is a post-order traversal?
Traverse left subtree, traverse right subtree, visit root
How do you delete a leaf node?
Remove the node
How do you delete a node with one child?
Remove that node
Link child to the parent node of the node removed
How do you delete a node with two children?
Find a node that will preserve search tree properties and put it in the place of the deleted node
Node with the next largest key
What are hash tables used for?
Quickly retrieve data from a large data set
Enabling efficient searching and maintaining of the hash table (adding, updating, deleting)
How does a hash table work?
Use key value pairs
Key generated from data that needs to be stored and then put through hash function/algorithm producing an address, which is the address in the array where data should be stored
When retrieving data, same process followed and data can be instantly retrieved from address produced by hash function no matter size of array
What should an effective hash table always have?
Free space
What is hashing?
Applying a hashing algorithm (or hash function) to a key
How is a hash table implemented?
Using an array because have to able to access each position of the array directly, which is done by specifying index of position within the array
What are buckets?
Positions within an array in a hash table, each used to store data (can be single piece or more complex object like record)
What is a key in a hash table?
Generated from data that needs to be stored
Must be stored as part of, or alongside, the data
Why must the size of the array for a hash table be planned carefully?
Must be big enough to store all data but not so large that you waste table
When is a hash table used?
When speed of insertion, deleting and looking up is a priority
What is a hash function?
Algorithm that converts hash key to hash values
Good hash function essential for effective performance of hash table
Must be designed and tested to minimise number of possible collisions
What are the requirements of a hash function?
Always produce same hash value for same key
Perform uniform distribution of hash values, meaning that every value has equal probability of being generated
Minimise clustering, which arises when many different keys produce the same hash value
Be very fast to compute
How is data inserted into a hash table?
Use hash function to generate index of position in the array that will be used to store data
Key must be stored as part of, or alongside, data
What is a collision in a hash table?
When two or more different keys produce the same hash value
Greater the LOAD FACTOR, greater chance of collisions
What is the load factor?
How full the hash table is
Why are collisions a problem?
Cannot store two sets of data at the same location
How are collisions dealt with?
Linear probing
Chaining
What is linear probing?
When key creates hash value that references a position that is already occupied, place data in next free position in hash table
Can probe sequentially or use an interval until empty bucket is found (SKIP FACTORING)
Each time this is done, increase likelihood of further collisions (clustering)
How is data retrieved when linear probing is used?
Hash key to generate index value
Examine indexed position to see if key (stored together with data) matches key of data looking for
If no match, check each location that follows (at appropriate interval) until matching record found
If reach empty bucket without finding matching key, data not in hash table
What is the problem with linear probing?
Significantly reduces efficiency of using hash table for searching
Worst case - have to inspect every position of the array
Why it’s important to design hash table to have extra capacity so hopefully algorithm will find free position not far from correct place
What is chaining?
Using linked lists
How does chaining work?
Instead of storing actual data in hash table, store pointer to location where data stored
Each data item stored as node with key value, data and pointer to next node
First value to be stored will have Null pointer as only item in list
When collision, pointer for next node at that location updated to point to new node
Creates chain of nodes whose keys resolve to the same hash value
How is data retrieved when chaining is used?
Hash key to generate index value
Examine indexed position to get pointer to node at head of list
Examine key of node to see if matches key looking for
If not node looking for, follow linked list until find node look for
If end of list reached without finding matching key (or head pointer is Null), data not in hash table
What is the worst case scenario using chaining
Every key hashes to same value and have to carry out linear search
What problem is rehashing used to address?
Over time, items added and deleted from hash table
If hash table starts to fill up or large number of items in wrong place, performance of hash table will degrade
What is rehashing?
New hash table is created (larger if needed)
Key for each item in existing table rehashed and item inserted into new hash table
If new table larger, hashing algorithm modified to generate larger range of value
Opportunity to review overall effectiveness of hash function and review how collisions handled
What are some alternative hashing algorithms?
All hashing algorithms involve mod function at some point as hash address has to be range of table addresses
Mid square
Folding method
How are deletions dealt with in a hash table?
Items to be deleted must be replaced with dummy item or marker
When searching for item which hashes to that spot, if not found, search will continue until it’s found or free space located
If new item is to be added and address contains dummy item, will replace dummy
What is a logic gate?
Fundamental component of a digital circuit
Each gate has one or more inputs and produces single output that depends on the inputs
Multiple can be combined to make complex circuits to carry out processing
What is a logic circuit?
Multiple logic gates combined
What are the inputs of a logic circuit?
Determined by voltage that flows around the system
High voltage = 1/True
Low voltage = 0/False
What is the output conventionally labelled as in a logic circuit?
Q
What is an AND gate?
Looks like a D
Both inputs have to be true for the output to be true
What is an example expression for an AND gate?
Y = A ∧ B
What is an OR gate?
Looks like an umbrella
Either inputs must be true for the output to be true
What is an example expression for an OR gate
Y = A ∨ B
What is a NOT gate?
Looks like a triangle with a dot on the end
Reverses the input
What is an example expression for a NOT gate?
Y = ¬A
What is an XOR gate?
OR gate with an additional line
Either inputs but not both must be true for output to be true
What is an example expression for an XOR gate?
Y = A ∨ B
But with OR symbol underlined
What is the order of precedence of logic gates?
NOT
AND
OR
What is a truth table?
Shows all possible inputs and outputs from a logic gate or circuit
Inputs can be expressed in any order
What the Boolean notation for the Boolean expression (A AND B) OR NOT (D AND E)?
(A ∧ B) V ¬(D ∧ E)
What is a Karnaugh map?
Version of a truth table for a Boolean expression that’s laid out in a way that makes it easier to simplify
What are the rules for groups in Karnaugh maps?
Sizes of groups must be to the power of 2 (2, 4, 8)
Groups should be as large as possible
Every 1 must be included in a group
Groups can overlap each other
Groups can wrap around sideways and top to bottom
How are Boolean expressions simplified?
Manipulated algebraically to form simpler expressions that implement the same logic
Why should Boolean expressions be simplified?
Allow simpler circuit to be produced with fewer logic gates
Reduce cost of circuit
Reduce amount of heat generated
Reduce processing time
What is another word for an AND logic gate?
Conjunction
What is another word for an OR logic gate?
Disjunction
What is another word for an XOR logic gate?
Exclusive disjunction
What is another word for a NOT logic gate?
Negation
What is equivalence?
The same as
What is the symbol for equivalence?
≡
What is De Morgan’s law?
Either logical function AND or OR may be replaced by the other, given certain changes to the equation
How does De Morgan’s law apply to Boolean expressions?
¬(A v B) ≡ ¬A ^ ¬B
¬(A ^ B) ≡ ¬A v ¬B
What is the distribution law?
Allows for the multiplying or factoring out of an expression
What must be true to use the distribution law?
Term outside the brackets doesn’t appear inside the brackets
Operator is different
How does the distribution law apply to Boolean expressions?
X ^ (Y v Z) ≡ (X ^ Y) v (X ^ Z)
X v (Y ^ Z) ≡ (X v Y) ^ (X v Z)
What is the association law?
Allows for removal of brackets from an expression and the regrouping of variables
What must be true to use the association law?
Term outside the brackets doesn’t appear inside the brackets
Operator is the same
How does the association law apply to Boolean expressions?
X ^ (Y ^ Z) ≡ (X ^ Y) ^ Z ≡ X ^ Y ^ Z
What is the double negation rule?
Two negatives make a positive
How does the double negation rule apply to Boolean expressions?
¬¬A ≡ A
What is the absorption rule?
The second term inside the bracket can always be eliminated and absorbed by the term outside the bracket
What must be true to use the absorption law?
Term outside the brackets appears inside the brackets
Operators must be different
How does the absorption rule apply to Boolean expressions?
X v (X ^ Y) ≡ X
X ^ (X v Y) ≡ X
X v X ^ Y ≡ X
What are the general rules using AND?
X ^ 0 ≡ 0
0 ^ X ≡ 0
X ^ 1 ≡ X
X ^ X ≡ X
X ^ ¬X ≡ 0
What are the general rules using OR
X v 0 ≡ X
0 V X ≡ X
X v 1 ≡ X
X v X ≡ X
X v ¬X ≡ 1
What is (A ᴧ ¬B) v B simplified?
(A v B) ^ (B v ¬B)
(A v B) ^ 1
(A v B)
What is A ^ B ^ ¬C V A ^ ¬C simplified?
(A ^ B ^ ¬C) v (A ^ ¬C)
D = A ^ ¬C
(D ^ B) v D
D
A ^ ¬C
What is ¬B ^ ¬(¬A V ¬B) simplified?
¬B ^ (A v B)
(¬B ^ A) v (¬B ^ B)
(¬B ^ A ) v 0
¬B ^ A
What is a flip flop?
Elemental sequential logic circuit that can store on bit and flip between two states, 0 and 1
What is D-type flip flop?
Synchronous sequential circuit that can be used to store the value of single binary digit
Has internal loop, allowing the previous output value to be stored
What are the two external inputs of a D-type flip flop?
Data signal (D)
Clock signal
What happens in a D-type flip flop when the clock signal is low (0)?
Changes at D make no difference to output
What happens in a D-type flip flop when the clock signal is high (1)?
Value of input D will appear at output Q
What are the problems with a D-type flip flop?
If there are changes in the data during the period when the clock signal is high, output at Q will chance in line with D, which might not be a desirable feature of the circuit
What is an edge-triggered D-type flip flop?
Introduces delay in processing the clock signal
D is only processed at rising edge of each signal change from the clock
On rising edge of each clock signal, state of D is accepted at output Q (updated to reflect this
Once clock signal input goes low, state of circuit won’t change and will continue to output (thus store) whatever value was already present on its output
What is the clock needed for in a flip flop?
Synchronising change of state of flip flop circuits
What are D-type flip flops used for?
Creating registers
Shift operations (multiplication and division)
Intermediate storage needed during arithmetic operation
Static RAM
What is static RAM?
Faster and more expensive than regular dynamic RAM, which must be periodically refreshed
Typically used for cache memory which DRAM used for main memory
What is a half adder?
Circuit that performs the addition of two bits
Takes input of two bits (A and B) and outputs the sum (S) and the carry (C)
What logic is the carry column produced by?
A AND B
What logic is the sum column produced by?
A XOR B
What is the problem with a half-adder?
Only has two inputs so cannot use the carry from a previous addition as a third input to a subsequent addition
Can only add 1-bit numbers
What is a full adder?
Combines two half-adders
Three inputs of A, B and carry bit Cin
Two outputs of S and Cout
Why would full adders be concatenated?
To add numbers together where each has multiple bits
