Computer Systems
Class XI CS · Class XI IP

Computer Systems

What a computer is made of, how it stores and processes data, the software that runs it, and the binary, logic and codes underneath.

7 chapters23 topics11-CS · Unit 111-IP · Unit 1
INPUTkey 'A' ENCODEA = 1000001 MEMORYRAM · cache CPUALU · CU SOFTWAREOS · apps OUTPUTon screen Underneath every step: binary numbers, and logic gates that work on them.
8 bits
= 1 byte
1 KB = 1024 bytes, and each unit up is 1024 times bigger
2ⁿ rows
Truth table
2 inputs → 4 rows; 3 inputs → 8 rows
45 = 101101₂
Number systems
= 55₈ = 2D₁₆: the same value in four bases
1–4 bytes
UTF-8
ASCII letters take 1 byte; Hindi letters 3
Chapter 1 of 7 · ORG

Computer Organisation

A computer is an electronic device that takes data as input, processes it following instructions, stores it, and gives output. This chapter covers how computers developed and what parts they are made of.

    ORG.01 · Computer Organisation

    Evolution of Computing Devices

    11-CS11-IP

    Computing devices grew from hand tools for counting into the fast electronic computers we use today. Each step made calculation faster and more automatic.

    c. 3000 BCEAbacusbeads1642Pascalinegears1834AnalyticalBabbage1946ENIACvacuum tubes1971Intel 4004CPU on a chiptodayPhones, AIeverywhere
    Each step replaced human effort with machines: hands → gears → punched cards → electronics → a whole CPU on one chip.
    Device / ideaWhenWhat it did
    AbacusAbout 3000 BCEBeads on rods for adding and subtracting by hand
    Pascaline (Blaise Pascal)1642Mechanical calculator using gears; could add and subtract
    Stepped Reckoner (Leibniz)1673Mechanical calculator that could also multiply and divide
    Jacquard loom1801Used punched cards to control weaving patterns: the first "program"
    Analytical Engine (Charles Babbage)1834 (designed)A general-purpose mechanical computer with memory and a processing unit. Babbage is called the "father of the computer"
    Tabulating machine (Herman Hollerith)1890Read punched cards to count the US census
    Turing machine (Alan Turing)1936A model of computation that defined what a computer can do
    ENIAC1946One of the first general-purpose electronic computers, using vacuum tubes
    Von Neumann architecture1945The stored-program idea: instructions and data kept together in memory. Most computers still use it
    Microprocessor (Intel 4004)1971A whole CPU on a single chip, which made personal computers possible

    Generations of computers

    GenerationPeriodMain technology
    First1940s–1950sVacuum tubes: huge, hot, used a lot of power
    Second1950s–1960sTransistors: smaller, faster, more reliable
    Third1960s–1970sIntegrated circuits (many transistors on one chip)
    Fourth1970s–todayMicroprocessors and VLSI: personal computers, laptops, phones
    FifthToday and aheadArtificial intelligence, parallel processing
    ORG.02 · Computer Organisation

    Components of a Computer System

    11-CS11-IP

    Every computer has four main parts: an input unit, a CPU that processes, memory that stores, and an output unit.

    CPU INPUTkeys, mouse ALUcalculates CUcontrols REGISTERS OUTPUTscreen, print MEMORYRAM, storage system bus: data, address, control
    Data flows from input to the CPU, which works with memory and sends results to output. The wires that connect the parts are the system bus.

    Hardware #hardware

    Hardware is every physical part of a computer that you can touch: the CPU, memory chips, hard disk, keyboard, monitor, printer and cables.

    Software #software

    Software is the set of programs (instructions) that tell the hardware what to do: the operating system, apps and games. Hardware without software cannot do anything useful; software needs hardware to run on. Chapter 3 covers software in detail.

    Interconnections: the system bus 11-IP #interconnections

    The parts of a computer are connected by a set of wires called the system bus. It has three parts:

    BusCarriesDirection
    Data busThe actual data being movedBoth ways
    Address busThe memory location to read from or write toCPU → memory
    Control busControl signals such as read, write and clockBoth ways
    ORG.03 · Computer Organisation

    CPU

    11-CS11-IP

    The CPU (Central Processing Unit) is the "brain" of the computer: it carries out the instructions of programs. In a modern computer it is a single chip called a microprocessor.

    PartJob
    ALU (Arithmetic Logic Unit)Does arithmetic (+, −, ×, ÷) and logical comparisons (>, <, =, AND, OR)
    CU (Control Unit)Reads each instruction, decodes it, and tells the other parts what to do and when
    RegistersTiny, very fast storage inside the CPU for the data and instruction being worked on right now

    The CPU repeats the fetch → decode → execute cycle billions of times a second. Its speed is measured in gigahertz (GHz). A CPU with several cores can run several tasks at the same time.

    1 · FETCHget next instruction2 · DECODECU reads its meaning3 · EXECUTEALU does itrepeats billions of times a second
    The instruction cycle: the CPU fetches an instruction from memory, the CU decodes it, the ALU executes it, and the cycle starts again.
    Exam tip

    "Which part of the CPU does calculations?" → ALU. "Which part directs the flow of data and instructions?" → CU.

    ORG.04 · Computer Organisation

    Input and Output Devices

    11-CS11-IP

    Input devices #input

    An input device sends data or commands into the computer, turning them into a form the computer can process.

    Keyboard, mouse, touchscreen, scanner, microphone, webcam, joystick, barcode reader, biometric (fingerprint) sensor, OMR (reads marked answer sheets), MICR (reads the magnetic numbers on cheques).

    Output devices #output

    An output device takes processed data out of the computer and shows it in a form people can use: a picture, print, sound or movement.

    Monitor, printer (inkjet, laser), speakers, headphones, projector, plotter (large drawings), 3D printer.

    Note

    Some devices do both. A touchscreen takes your touch as input and shows output. A modem and a headset with a microphone are others.

    Chapter practice · ORG

    Check your understanding

    Which part of the CPU performs calculations and comparisons?
    Which of these is an output device?
    The device that reads answers marked on an exam answer sheet is:
    The first generation of computers used:
    Which bus carries the memory location the CPU wants to read?
    Your score
    – / 5
    Answer every question to see your score.

    One-page revision

    BabbageAnalytical Engine; father of the computer
    Generationstubes → transistors → ICs → microprocessors → AI
    Hardware / softwarephysical parts / programs
    CPUALU + CU + registers
    Fetch–decode–executethe CPU's cycle
    Input / outputinto / out of the computer
    System busdata · address · control
    Chapter 2 of 7 · MEM

    Computer Memory

    Memory is where a computer keeps data and instructions. Different kinds trade off speed, size and cost, and some lose their contents when the power goes off.

      MEM.01 · Computer Memory

      Types of Memory

      11-CS11-IP
      REGISTERS CACHE RAM (primary) SSD · HDD · pen drive faster,costlier bigger,cheaper
      The memory hierarchy. Registers and cache are inside or next to the CPU; RAM is the main memory; secondary storage keeps everything permanently.

      Primary memory #primary

      Primary memory is the main memory that the CPU reads from directly. It holds the programs and data in use right now.

      RAM (Random Access Memory)ROM (Read Only Memory)
      Contents when power is offLost: volatileKept: non-volatile
      Can be written?Yes, all the timeNormally only read
      HoldsPrograms and data being used nowStart-up instructions (firmware, BIOS)
      SizeLarge (e.g. 8–16 GB)Small

      Cache memory #cache

      Cache is a small, very fast memory between the CPU and RAM. It keeps copies of the data and instructions the CPU uses most often, so the CPU doesn't have to wait for the slower RAM. It is faster and costlier than RAM, and much smaller.

      CPUneeds dataCACHEsmall, fastRAMbig, slower1 · look in cache2 · only on a misscopy kept in cachehit: answered fast
      A cache hit (the data is already in the cache) is fast. On a miss, the data comes from RAM and a copy is kept in the cache for next time.

      Secondary memory #secondary

      Secondary memory (storage) keeps data permanently, even when the computer is off. The CPU cannot use it directly; data is first copied into RAM. Examples: hard disk drive (HDD), solid state drive (SSD), pen drive, memory card, CD/DVD.

      Primary (RAM)Secondary
      Volatile?YesNo
      SpeedFastSlower
      Size and costSmaller, costlier per GBLarger, cheaper per GB
      Used by the CPUDirectlyThrough RAM
      MEM.02 · Computer Memory

      Units of Memory

      11-CS11-IP

      All memory is measured in bits and bytes. Each unit after the byte is 1024 times the one before, because computers count in powers of 2 and 210 = 1024.

      bit0 or 1byte= 8 bitsKB= 1024 BMB= 1024 KBGB= 1024 MBTB= 1024 GBPB= 1024 TBeach step up is 1024 times bigger (a byte is 8 bits)
      Going up a step, divide by 1024; going down a step, multiply by 1024. Between bit and byte the factor is 8.

      Bit #bit

      A bit (binary digit) is the smallest unit: a single 0 or 1. Four bits make a nibble.

      Byte #byte

      A byte is 8 bits, enough to store one character such as 'A'.

      KB: kilobyte #kb

      1 KB = 1024 bytes. A short text file.

      MB: megabyte #mb

      1 MB = 1024 KB. A photo or a song.

      GB: gigabyte #gb

      1 GB = 1024 MB. A film; the RAM in a phone.

      TB: terabyte #tb

      1 TB = 1024 GB. A large hard disk.

      PB: petabyte #pb

      1 PB = 1024 TB. The storage of a big data centre.

      Python · check the sizes
      size = 1
      for unit in ['KB', 'MB', 'GB', 'TB', 'PB']:
          size = size * 1024
          print(f'1 {unit} = {size:,} bytes')
      Output
      1 KB = 1,024 bytes 1 MB = 1,048,576 bytes 1 GB = 1,073,741,824 bytes 1 TB = 1,099,511,627,776 bytes 1 PB = 1,125,899,906,842,624 bytes
      UnitEquals
      1 byte8 bits
      1 KB1024 bytes
      1 MB1024 KB
      1 GB1024 MB
      1 TB1024 GB
      1 PB1024 TB
      Exam tip

      To change units, multiply by 1024 going down (GB → MB) and divide by 1024 going up. For example, 2 GB = 2 × 1024 = 2048 MB, and 1 KB = 1024 × 8 = 8192 bits.

      MEM.03 · Computer Memory

      Data Deletion and Recovery

      11-IP

      Data deletion #deletion

      Deleting a file usually moves it to the Recycle Bin (or Trash), from where it can be restored. Even after you empty the bin or press Shift + Delete, the data is not wiped: the operating system only marks that space as free, and the old bits stay on the disk until new data is written over them.

      1 · SAVEDP1P2P3P4photo.jpg stored in four blocks2 · DELETEDP1P2P3P4blocks only marked free; the photo is still there3 · NEW FILEN1N2P3P4N1, N2 replaced P1, P2; P3, P4 still recoverable
      Dashed blocks are marked free but still hold the old data. Only data that has been overwritten is really gone.

      Data recovery #recovery

      Data recovery means getting back deleted, lost or damaged data. Because deleted data often stays on the disk, recovery software can find and restore it, as long as it hasn't been overwritten. Regular backups (on another drive or the cloud) are the safest way to make sure data can be recovered.

      Security concerns #security

      The same fact is a risk: if you sell, give away or throw out an old phone, computer or pen drive, someone can recover your photos, messages and passwords from it.

      • Use data-shredding software that overwrites the deleted space several times.
      • Encrypt the device, then do a factory reset before giving a phone away.
      • Physically destroy a storage device that held very sensitive data.
      Chapter practice · MEM

      Check your understanding

      Which memory loses its contents when the power is switched off?
      The small, fast memory between the CPU and RAM is:
      How many MB are there in 4 GB?
      1 byte is equal to:
      Why can "permanently deleted" files often be recovered?
      Your score
      – / 5
      Answer every question to see your score.

      One-page revision

      RAMmain memory; volatile
      ROMstart-up program; non-volatile
      Cachebetween CPU and RAM; fastest after registers
      SecondaryHDD, SSD, pen drive; permanent
      Hierarchyregisters → cache → RAM → storage
      8 bits= 1 byte; 4 bits = nibble
      × 1024KB → MB → GB → TB → PB
      Deleted ≠ wipedrecoverable until overwritten
      Chapter 3 of 7 · SW

      Software

      The programs that make the hardware useful, sorted by what they are for.

        SW.01 · Software

        Purpose of Software

        11-CS11-IP

        Software is a set of instructions (programs) that tells the hardware what to do. Its purposes are to run and manage the computer itself, to help people do tasks such as writing, calculating or browsing, and to help programmers create new software.

        TypePurposeExamples
        System softwareRuns and manages the computerWindows, Linux, antivirus, device drivers
        Programming tools and translatorsHelp write and translate programsPython interpreter, C++ compiler, IDE
        Application softwareDoes a task for the userBrowser, word processor, games
        SW.02 · Software

        System Software

        11-CS11-IP

        System software works directly with the hardware and provides a base on which other software runs. Users rarely use it on its own.

        Operating system #operating-system

        The most important system software: it manages the hardware and lets users and apps use it. Examples: Windows, Linux, macOS, Android, iOS. Chapter 4 covers it in detail.

        System utilities #utilities

        Small programs that maintain and protect the computer: antivirus, disk cleanup, disk defragmenter, backup tools, file compression (zip), and task manager.

        Device drivers #device-drivers

        A device driver lets the operating system talk to one particular hardware device, such as a printer, webcam or graphics card. It acts as a translator between the OS and the device. Without the right driver, a device may not work.

        APPyou press PrintOSpasses the jobDRIVERprinter commandsPRINTERprints the page
        The app and the OS don't need to know how each printer works: the driver handles that one device.
        SW.03 · Software

        Programming Tools and Language Translators

        11-CS11-IP

        A computer only understands machine language: instructions written in binary (0s and 1s). People write programs in a high-level language such as Python or C++ (easy to read) or in assembly language (short codes such as ADD, MOV). A language translator turns these into machine language. Programming tools such as code editors, debuggers and IDEs (Integrated Development Environments, e.g. IDLE) help write and test programs.

        Assembler #assembler

        Translates assembly language into machine language.

        Compiler #compiler

        Translates the whole high-level program at once into machine code (an object or .exe file), and lists all the errors it finds. The translated program can then run again and again without the compiler. C and C++ use compilers.

        Interpreter #interpreter

        Translates and runs a high-level program one line at a time, and stops at the first error. It translates again every time the program runs. Python uses an interpreter.

        SOURCEwhole program COMPILERtranslate all OBJECT CODEsaved .exe RUNany time, fast SOURCEline by line INTERPRETER1 line, run it RUN THAT LINE, THEN NEXTstops at the first error Python works like the lower row.
        A compiler translates once and the result runs on its own; an interpreter translates every time the program runs.
        CompilerInterpreter
        TranslatesThe whole program at onceOne line at a time
        ErrorsListed together after translatingStops at the first error
        OutputSaves an object (machine code) fileNo separate file
        Running speedFaster, once compiledSlower: translates each time
        LanguagesC, C++Python
        SW.04 · Software

        Application Software

        11-CS11-IP

        Application software (apps) does a particular task for the user, running on top of the operating system. Examples: web browsers, word processors, spreadsheets, presentation software, photo editors, media players and games.

        SW.05 · Software

        Generic and Specific Purpose Software

        11-CS11-IP
        Generic (general purpose)Specific purpose (customised)
        Made forMany users with common needsOne organisation or one particular job
        Bought asA ready product, off the shelfMade to order
        CostLow, shared by many usersHigher
        ExamplesWord processor, spreadsheet, browser, photo editorSchool fee and result system, railway reservation, hospital records, payroll of a company
        Chapter practice · SW

        Check your understanding

        What kind of software is it?

        A program that lets Windows use a new printer.

        A program that scans files and removes viruses.

        Software a school had made to manage its fees and results.

        A spreadsheet program sold to millions of users.

        Self-check quiz

        Which translator converts and runs a program one line at a time?
        Assembly language is translated by a(n):
        Which is an example of system software?
        A compiler shows errors:
        Your score
        – / 4
        Answer every question to see your score.

        One-page revision

        System softwareOS, utilities, drivers
        Utilitiesantivirus, cleanup, backup, zip
        Device driverOS ↔ one device
        Assemblerassembly → machine code
        Compilerwhole program; saved .exe; C, C++
        Interpreterline by line; stops at error; Python
        Applicationdoes a user's task
        Generic / specificoff the shelf / made to order
        Chapter 4 of 7 · OS

        Operating System

        The operating system (OS) is the system software that manages the computer's hardware and software and lets the user work with it. It is the first program to load when the computer starts.

          OS.01 · Operating System

          Functions of the Operating System

          11-CS
          USER APPLICATIONS · browser, games, editor OPERATING SYSTEM · Windows, Linux, Android HARDWARE · CPU, memory, devices
          The OS sits between applications and the hardware: apps ask the OS, and the OS controls the hardware.
          FunctionWhat the OS does
          Process managementStarts and stops programs, and shares the CPU between running programs so they seem to run at the same time
          Memory managementGives each program the part of RAM it needs, and takes it back when the program closes
          File managementOrganises files and folders on storage: create, open, save, copy, delete, and who may use them
          Device managementControls input/output devices through their drivers, e.g. sends a document to the printer
          Security and user managementUser accounts and passwords, and keeps one user's or program's data safe from another
          User interfaceGives the user a way to give commands (next topic)
          OS.02 · Operating System

          OS User Interface

          11-CS

          The user interface (UI) is how a person gives commands to the OS and sees the results.

          InterfaceHow you use itExample
          Command line (CLI)Type text commands at a promptMS-DOS, Linux terminal (ls, cd)
          Graphical (GUI)Click windows, icons, menus with a pointerWindows, macOS, Ubuntu desktop
          Touch-basedTap, swipe and pinch on a screenAndroid, iOS
          Voice-basedSpeak commandsVoice assistants
          Gesture-basedHand or body movements read by a camera or sensorSome smart TVs, game consoles
          Exam tip

          CLI vs GUI: a CLI needs you to remember and type commands but uses few resources; a GUI is easier to learn but needs more memory and processing.

          Chapter practice · OS

          Check your understanding

          Sharing the CPU between running programs is the OS's:
          Typing cd Documents at a prompt uses a:
          Giving each program its share of RAM is:
          Your score
          – / 3
          Answer every question to see your score.

          One-page revision

          Processstart, stop, share the CPU
          Memorygive and take back RAM
          Fileorganise files and folders
          Devicecontrol I/O through drivers
          Securityusers, passwords, protection
          CLI · GUI · touch · voiceways to give commands
          Chapter 5 of 7 · BOOL

          Boolean Logic

          Boolean logic works with only two values: 1 (true, on, high) and 0 (false, off, low). Every calculation inside a CPU is built from simple logic operations on these two values.

            BOOL.01 · Boolean Logic

            Logic Gates

            11-CS

            A logic gate is an electronic circuit that takes one or more binary inputs and gives one binary output by a fixed rule. In expressions, · means AND, + means OR, and a bar or ' means NOT (A' is read "A bar" or "not A").

            AYNOTY = A'ABYANDY = A·BABYORY = A + BABYNANDY = (A·B)'ABYNORY = (A + B)'ABYXORY = A ⊕ B
            The symbols for the six gates. A small circle (bubble) on the output means NOT.
            Python · every gate for every input
            print(' A B | AND OR NAND NOR XOR')
            for A in (0, 1):
                for B in (0, 1):
                    AND = A & B
                    OR = A | B
                    print(f' {A} {B} |  {AND}   {OR}   {1 - AND}    {1 - OR}   {A ^ B}')
            Output
            A B | AND OR NAND NOR XOR 0 0 | 0 0 1 1 0 0 1 | 0 1 1 0 1 1 0 | 0 1 1 0 1 1 1 | 1 1 0 0 0

            NOT #not

            One input. The output is the opposite of the input: 0 → 1, 1 → 0. Y = A'. Also called an inverter.

            AND #and

            Output is 1 only when all inputs are 1. Y = A·B. Like two switches in series: the bulb glows only if both are on.

            OR #or

            Output is 1 when at least one input is 1. Y = A + B. Like two switches in parallel.

            NAND #nand

            NOT of AND: output is 0 only when all inputs are 1. Y = (A·B)'.

            NOR #nor

            NOT of OR: output is 1 only when all inputs are 0. Y = (A + B)'.

            XOR #xor

            Exclusive OR: output is 1 when the inputs are different, and 0 when they are the same. Y = A ⊕ B = A'·B + A·B'.

            Note

            NAND and NOR are called universal gates: any other gate, and so any circuit, can be built using only NAND gates (or only NOR gates).

            BOOL.02 · Boolean Logic

            Truth Tables

            11-CS

            A truth table lists the output of a gate or expression for every possible combination of inputs. With n inputs there are 2n rows: 2 inputs → 4 rows, 3 inputs → 8 rows.

            1. Write all input combinations, counting in binary: 000, 001, 010 … 111.
            2. Add a column for each part of the expression, working from the innermost part out.
            3. Fill each column row by row; the last column is the output.

            For Y = A·B + C' (3 inputs, so 8 rows):

            Python · build the table
            print(' A B C | A.B  C\'  Y = A.B + C\'')
            for A in (0, 1):
                for B in (0, 1):
                    for C in (0, 1):
                        AB = A & B
                        nC = 1 - C
                        print(f' {A} {B} {C} |  {AB}   {nC}      {AB | nC}')
            Output
            A B C | A.B C' Y = A.B + C' 0 0 0 | 0 1 1 0 0 1 | 0 0 0 0 1 0 | 0 1 1 0 1 1 | 0 0 0 1 0 0 | 0 1 1 1 0 1 | 0 0 0 1 1 0 | 1 1 1 1 1 1 | 1 0 1
            BOOL.03 · Boolean Logic

            De Morgan's Laws

            11-CS

            De Morgan's laws show how to take NOT of an AND or an OR: break the bar and change the sign.

            LawIn words
            (A + B)' = A' · B'NOT (A OR B) = (NOT A) AND (NOT B)
            (A · B)' = A' + B'NOT (A AND B) = (NOT A) OR (NOT B)

            To prove a law, make a truth table with both sides as columns. If the two columns match in every row, the law holds.

            Python · prove both laws
            print(' A B | (A+B)\'  A\'.B\' | (A.B)\'  A\'+B\'')
            for A in (0, 1):
                for B in (0, 1):
                    nA, nB = 1 - A, 1 - B
                    print(f' {A} {B} |   {1 - (A | B)}       {nA & nB}   |   {1 - (A & B)}      {nA | nB}')
            Output
            A B | (A+B)' A'.B' | (A.B)' A'+B' 0 0 | 1 1 | 1 1 0 1 | 0 0 | 1 1 1 0 | 0 0 | 1 1 1 1 | 0 0 | 0 0

            In both pairs of columns the values match in all 4 rows, so both laws are true. The laws also work for more variables: (A + B + C)' = A'·B'·C'.

            ABYABY=(A + B)' = A'·B' NOR = AND with inverted inputsABYABY=(A·B)' = A'+B' NAND = OR with inverted inputs
            The same laws as circuits: a bubble on the inputs means each input is inverted first. This is why NAND and NOR can stand in for other gates.
            Common mistake

            (A · B)' is not A' · B'. When the bar breaks, the sign must change: · becomes + and + becomes ·.

            BOOL.04 · Boolean Logic

            Logic Circuits

            11-CS

            A logic circuit joins gates so that the output of one becomes the input of another. Every Boolean expression can be drawn as a circuit, and every circuit can be written as an expression.

            Expression → circuit: draw a gate for each operation, innermost first. For Y = A·B + C':

            ABCYA·BC'A·B + C'
            A and B go into an AND gate; C goes into a NOT gate; their outputs go into an OR gate, giving Y = A·B + C'. Its truth table is in BOOL.02.

            Circuit → expression: work from the inputs towards the output, writing the output of each gate in terms of its inputs, until you reach the last gate.

            Exam tip

            Label the output of every gate on your drawing (A·B, C' …). It makes both the expression and the truth table easy to write, and earns step marks.

            Chapter practice · BOOL

            Check your understanding

            Logic gate lab

            Predict the output

            A = 1, B = 0, C = 1. What is Y = (A + B)·C'?

            Using De Morgan's law, simplify (A' + B')'.

            How many rows does the truth table of A·B + C·D have?

            Which gate gives 1 only when both inputs are 0?

            Self-check quiz

            The output is 1 only when the two inputs are different. The gate is:
            (A · B)' is equal to:
            Which are the universal gates?
            A truth table for 3 inputs has how many rows?
            Your score
            – / 4
            Answer every question to see your score.

            One-page revision

            NOTY = A'; flips
            ANDY = A·B; 1 if all 1
            ORY = A+B; 1 if any 1
            NAND(A·B)'; 0 only if all 1
            NOR(A+B)'; 1 only if all 0
            XORA⊕B; 1 if different
            2ⁿ rowstruth table for n inputs
            De Morgan(A+B)' = A'·B' ; (A·B)' = A'+B'
            UniversalNAND, NOR
            Chapter 6 of 7 · NUM

            Number System

            A number system is a way of writing numbers with a set of digits. Its base (or radix) is the number of digits it uses. Computers work in base 2, and bases 8 and 16 are short ways of writing binary.

              NUM.01 · Number System

              Number Systems

              11-CS

              In every system, each digit's value depends on its position: the rightmost digit is worth base0 = 1, the next base1, then base2, and so on. To show which base a number is in, write the base as a small number after it: 1012, 558, 4510, 2D16.

              SystemBaseDigitsPlace values
              Binary20, 1… 8 4 2 1
              Octal80–7… 512 64 8 1
              Decimal100–9… 1000 100 10 1
              Hexadecimal160–9, A–F (A = 10 … F = 15)… 4096 256 16 1

              Binary #binary

              Base 2, digits 0 and 1. Computers use it because an electronic switch has two states: off (0) and on (1).

              Octal #octal

              Base 8, digits 0–7. One octal digit stands for exactly 3 binary digits.

              Decimal #decimal

              Base 10, digits 0–9: the system people use every day.

              Hexadecimal #hexadecimal

              Base 16, digits 0–9 and A–F. One hex digit stands for exactly 4 binary digits, so it is a short way to write long binary numbers, such as memory addresses and colour codes (#FF0000 is red).

              The first 16 numbers in all four systems:

              Python
              print('Dec  Bin   Oct  Hex')
              for n in range(16):
                  print(f'{n:>3}  {n:04b}  {n:>3o}  {n:>3X}')
              Output
              Dec Bin Oct Hex 0 0000 0 0 1 0001 1 1 2 0010 2 2 3 0011 3 3 4 0100 4 4 5 0101 5 5 6 0110 6 6 7 0111 7 7 8 1000 10 8 9 1001 11 9 10 1010 12 A 11 1011 13 B 12 1100 14 C 13 1101 15 D 14 1110 16 E 15 1111 17 F
              NUM.02 · Number System

              Conversion Between Number Systems

              11-CS
              DECIMALbase 10 BINARYbase 2 OCTALbase 8 HEXbase 16 ÷ 2, remainders ↑ × powers of 2, add groupsof 3 groupsof 4
              Every route works both ways. Decimal ↔ octal and decimal ↔ hex use the same methods with 8 and 16 instead of 2. Octal ↔ hex is easiest through binary.

              Decimal → binary, octal or hex: repeated division

              Divide by the new base and write down the remainder. Divide the quotient again, and repeat until the quotient is 0. The answer is the remainders read from bottom to top.

              Python · 45 to binary, step by step
              n = 45
              steps = []
              while n > 0:
                  steps.append(n % 2)
                  print(n, '÷ 2 =', n // 2, 'remainder', n % 2)
                  n = n // 2
              print('Read remainders bottom to top:',
                    ''.join(str(d) for d in reversed(steps)))
              Output
              45 ÷ 2 = 22 remainder 1 22 ÷ 2 = 11 remainder 0 11 ÷ 2 = 5 remainder 1 5 ÷ 2 = 2 remainder 1 2 ÷ 2 = 1 remainder 0 1 ÷ 2 = 0 remainder 1 Read remainders bottom to top: 101101

              The same way, 45 ÷ 8 = 5 r 5, so 45 = 558; and 45 ÷ 16 = 2 r 13 (D), so 45 = 2D16.

              Binary, octal or hex → decimal: place values

              Multiply each digit by its place value (baseposition, counting positions from 0 on the right) and add.

              2^5 = 321322^4 = 16002^3 = 8182^2 = 4142^1 = 2002^0 = 11132 + 8 + 4 + 1= 45
              Only the positions holding a 1 count. Write the place values above the digits first; it avoids mistakes.
              Python · 101101 to decimal
              bits = '101101'
              total = 0
              for power, d in enumerate(reversed(bits)):
                  print(f'{d} x 2^{power} = {int(d) * 2**power}')
                  total += int(d) * 2**power
              print('Total =', total)
              Output
              1 x 2^0 = 1 0 x 2^1 = 0 1 x 2^2 = 4 1 x 2^3 = 8 0 x 2^4 = 0 1 x 2^5 = 32 Total = 45

              Similarly 558 = 5×8 + 5 = 45, and 2D16 = 2×16 + 13 = 45.

              Binary ↔ octal and hex: grouping

              From binary, split the bits into groups from the right: groups of 3 for octal, 4 for hex. Add zeros on the left to fill the last group, then write each group as one digit. To go back, write each digit as 3 (or 4) bits.

              groups of 3 → octal0011011301021117= 1327 in octalgroups of 4 → hex001021101D01117= 2D7 in hexzeros were added on the left
              Always group from the right, and add zeros on the left to complete the last group.
              10110101112 toGroupsDigitsAnswer
              Octal (groups of 3)001 · 011 · 010 · 1111 · 3 · 2 · 713278
              Hex (groups of 4)0010 · 1101 · 01112 · D · 72D716
              Python · check it
              b = '1011010111'
              print('octal: groups of 3 ->', oct(int(b, 2)))
              print('hex  : groups of 4 ->', hex(int(b, 2)))
              print(int(b, 2))
              Output
              octal: groups of 3 -> 0o1327 hex : groups of 4 -> 0x2d7 727

              Octal ↔ hex: go through binary. 13278 → 001 011 010 111 → regroup in fours → 2D716.

              Numbers with a decimal point

              A number like 25.375 has a whole part (25) and a fraction part (.375). Convert the two parts separately, then join them with the point. The whole part uses the methods above; the fraction part needs the reverse idea.

              Decimal fraction → binary, octal or hex: repeated multiplication

              1. Multiply the fraction by the new base (2, 8 or 16).
              2. The whole-number part of the result is the next digit.
              3. Keep only the fraction part, and repeat until it becomes 0 or you have enough digits.
              4. Read the digits top to bottom: the opposite of division.
              Python · 0.625 to binary
              f = 0.625
              digits = ''
              for _ in range(3):
                  f = f * 2
                  print(f'x 2 = {f}  -> digit {int(f)}')
                  digits += str(int(f))
                  f = f - int(f)
              print('0.625 =', '0.' + digits, 'in binary')
              Output
              x 2 = 1.25 -> digit 1 x 2 = 0.5 -> digit 0 x 2 = 1.0 -> digit 1 0.625 = 0.101 in binary

              The same steps for 0.375 in all three bases. In base 8 and 16 it finishes in one step:

              Python
              for base in (2, 8, 16):
                  x, digits = 0.375, ''
                  while x > 0:
                      x = x * base
                      print(f'  x {base} = {x}  -> digit {int(x)}')
                      digits += '0123456789ABCDEF'[int(x)]
                      x = x - int(x)
                  print(f'0.375 = 0.{digits} in base {base}')
              Output
              x 2 = 0.75 -> digit 0 x 2 = 1.5 -> digit 1 x 2 = 1.0 -> digit 1 0.375 = 0.011 in base 2 x 8 = 3.0 -> digit 3 0.375 = 0.3 in base 8 x 16 = 6.0 -> digit 6 0.375 = 0.6 in base 16

              Join each answer to the whole part, converted the usual way (25 = 110012 = 318 = 1916):

              Python
              for base, name in ((2, 'binary'), (8, 'octal'), (16, 'hex')):
                  whole = format(25, 'b' if base == 2 else 'o' if base == 8 else 'X')
                  x, frac = 0.375, ''
                  while x > 0:
                      x *= base
                      frac += '0123456789ABCDEF'[int(x)]
                      x -= int(x)
                  print(f'25.375 = {whole}.{frac} in {name}')
              Output
              25.375 = 11001.011 in binary 25.375 = 31.3 in octal 25.375 = 19.6 in hex

              Binary, octal or hex fraction → decimal: negative powers

              Digits after the point have place values base-1, base-2, base-3 …, so multiply each by its place value and add, as for the whole part.

              NumberWorkingDecimal
              101.10124 + 0 + 1 + 1×2-1 + 0×2-2 + 1×2-3 = 5 + 0.5 + 0.1255.625
              31.383×8 + 1 + 3×8-1 = 25 + 3/825.375
              19.6161×16 + 9 + 6×16-1 = 25 + 6/1625.375
              A.81610 + 8×16-1 = 10 + 0.510.5
              Place after the pointBinaryOctalHex
              1st2-1 = 0.58-1 = 0.12516-1 = 0.0625
              2nd2-2 = 0.258-2 = 0.01562516-2 = 0.00390625
              3rd2-3 = 0.1258-316-3
              Python · check the answers
              def to_decimal(s, base):
                  whole, _, frac = s.partition('.')
                  value = int(whole, base)
                  for k, d in enumerate(frac, start=1):
                      value += int(d, base) * base ** -k
                  return value
              
              print(to_decimal('101.101', 2))
              print(to_decimal('31.3', 8))
              print(to_decimal('19.6', 16))
              print(to_decimal('A.8', 16))
              Output
              5.625 25.375 25.375 10.5

              Binary fraction ↔ octal or hex: group away from the point

              Grouping still works, but you start at the point: the whole part is grouped from the point leftwards (add zeros on the left), and the fraction part from the point rightwards (add zeros on the right).

              octal: groups of 3, starting at the point01130011..0113= 31.3 in octalhex: groups of 4, starting at the point0001110019..01106= 19.6 in hexdim zeros were added
              Padding zeros go on the outside: left of the whole part, right of the fraction part. A zero added on the right of a fraction doesn't change its value.

              Fractions that never end

              Some fractions never reach 0 when multiplied, just as 1/3 = 0.333… in decimal. 0.1 in binary repeats 0011 forever:

              Python
              x, digits = 0.1, ''
              for _ in range(12):
                  x *= 2
                  digits += str(int(x))
                  x -= int(x)
              print('0.1 =', '0.' + digits, '... in binary')
              Output
              0.1 = 0.000110011001 ... in binary

              In that case, stop after the number of places the question asks for (usually 4 to 6), and write "…" or say it is approximate.

              Common mistake

              For the whole part you divide and read remainders bottom to top; for the fraction part you multiply and read the whole-number parts top to bottom. Mixing these up reverses the digits.

              Checking with Python

              Python
              print(bin(45), oct(45), hex(45))
              print(int('101101', 2), int('55', 8), int('2D', 16))
              Output
              0b101101 0o55 0x2d 45 45 45

              bin(), oct() and hex() convert a decimal number and add a prefix (0b, 0o, 0x). int(text, base) converts the other way.

              Common mistake

              In repeated division, the remainders are read from the last to the first. Reading top to bottom gives 101101 backwards (101101 happens to be a palindrome; try 6: remainders 0, 1, 1 → 110, not 011).

              Chapter practice · NUM

              Check your understanding

              Base converter

              Steps
              Answer

              Whole part: divide, read remainders bottom to top. Fraction part: multiply, read digits top to bottom.

              Convert it

              Convert 2510 to binary.

              Convert 11102 to decimal.

              Convert 1101012 to octal and hex.

              Convert 12.7510 to binary.

              Convert 0.687510 to octal and to hex.

              Convert 110.0112 to decimal.

              Convert 1011.11012 to octal and hex.

              Convert A316 to decimal.

              Self-check quiz

              The base of the hexadecimal system is:
              Which is not a valid octal number?
              The binary number 1111 in decimal is:
              To convert a decimal fraction to binary, you:
              The value of the first digit after the point in octal is:
              Grouping 0.10112 in threes for octal gives:
              To convert binary to hexadecimal, group the bits in:
              Your score
              – / 7
              Answer every question to see your score.

              One-page revision

              Bases2 · 8 · 10 · 16
              Hex digits0–9, A=10 … F=15
              Dec → base÷ base, remainders bottom to top
              Base → decdigit × base^position, add
              Bin → oct / hexgroups of 3 / 4 from the right
              Fraction → base× base, whole parts top to bottom
              Base fraction → decdigit × base⁻¹, base⁻², …
              Group at the pointwhole part leftwards, fraction rightwards
              Never ends?stop at the places asked; write …
              Pythonbin · oct · hex · int(s, base)
              Chapter 7 of 7 · ENC

              Encoding Schemes

              A computer stores only numbers, so every character (letters, digits, symbols, other scripts) is given a number. An encoding scheme is the agreed table of which number stands for which character, and how that number is stored as bits.

                ENC.01 · Encoding Schemes

                ASCII

                11-CS

                ASCII (American Standard Code for Information Interchange) uses 7 bits, so it has 27 = 128 codes (0–127): English letters, digits, punctuation and some control codes. It covers only English. Extended ASCII uses 8 bits for 256 codes.

                Python · codes with ord() and chr()
                for ch in ['A', 'Z', 'a', '0', ' ']:
                    print(repr(ch), ord(ch), format(ord(ch), '07b'))
                print(chr(66), chr(98))
                Output
                'A' 65 1000001 'Z' 90 1011010 'a' 97 1100001 '0' 48 0110000 ' ' 32 0100000 B b
                CharactersCodes
                A–Z65–90
                a–z97–122 (lowercase = uppercase + 32)
                0–948–57
                Space32
                ENC.02 · Encoding Schemes

                ISCII

                11-CS

                ISCII (Indian Script Code for Information Interchange) is an 8-bit code (256 codes) for Indian scripts such as Devanagari, Bengali, Gurmukhi, Tamil and Telugu. Its first 128 codes are the same as ASCII; the other 128 hold the letters of Indian scripts. It was adopted as a standard by the Bureau of Indian Standards in 1991. Today, Unicode is used instead.

                ENC.03 · Encoding Schemes

                Unicode

                11-CS

                Unicode gives a unique number, called a code point, to every character of every writing system in the world, plus symbols and emoji. Code points are written U+ followed by hex: 'A' is U+0041 and 'अ' is U+0905. The first 128 code points are the same as ASCII. Unicode can be stored in different ways:

                UTF-8 #utf8

                A variable-length encoding: each character takes 1 to 4 bytes. ASCII characters take 1 byte (exactly as in ASCII), most Indian scripts take 3. It saves space for English text and is the most used encoding on the web.

                UTF-32 #utf32

                A fixed-length encoding: every character takes exactly 4 bytes (32 bits). Simple to process, because every character is the same size, but uses more space.

                UTF-8: 1 to 4 bytesUTF-32: always 4 bytesA4100000041éc3a9000000e9अe0a48500000905😀f09f98800001f600
                The actual bytes (in hex) for each character. English text in UTF-8 is the same as ASCII, one byte per letter.
                Python · bytes used
                for ch in ['A', 'é', 'अ', '😀']:
                    u8 = ch.encode('utf-8')
                    u32 = ch.encode('utf-32-be')
                    print(ch, f'U+{ord(ch):04X}',
                          'UTF-8:', len(u8), 'bytes', u8.hex(' '),
                          '| UTF-32:', len(u32), 'bytes')
                Output
                A U+0041 UTF-8: 1 bytes 41 | UTF-32: 4 bytes é U+00E9 UTF-8: 2 bytes c3 a9 | UTF-32: 4 bytes अ U+0905 UTF-8: 3 bytes e0 a4 85 | UTF-32: 4 bytes 😀 U+1F600 UTF-8: 4 bytes f0 9f 98 80 | UTF-32: 4 bytes
                ASCIIISCIIUTF-8UTF-32
                Bits per character788 to 32 (1–4 bytes)32 (4 bytes)
                Characters128256All of Unicode (over 1 lakh)
                CoversEnglishEnglish + Indian scriptsEvery language
                Exam tip

                Unicode is the character set (which number each character gets); UTF-8 and UTF-32 are ways of storing those numbers in bytes.

                Chapter practice · ENC

                Check your understanding

                How many characters can 7-bit ASCII represent?
                The ASCII code of 'A' is 65. What is the code of 'a'?
                Which encoding uses a fixed 4 bytes for every character?
                ISCII was made for:
                Your score
                – / 4
                Answer every question to see your score.

                One-page revision

                ASCII7-bit; 128 codes; English
                A · a · 0 · space65 · 97 · 48 · 32
                ISCII8-bit; Indian scripts; 1991
                Unicodea code point for every character
                UTF-81–4 bytes; ASCII-compatible
                UTF-32always 4 bytes
                ord() · chr()character ↔ code