<?xml version="1.0" encoding="UTF-8"?><rss xmlns:dc="http://purl.org/dc/elements/1.1/" xmlns:content="http://purl.org/rss/1.0/modules/content/" xmlns:atom="http://www.w3.org/2005/Atom" version="2.0" xmlns:cc="http://cyber.law.harvard.edu/rss/creativeCommonsRssModule.html">
    <channel>
        <title><![CDATA[Stories by Ruthu Rao on Medium]]></title>
        <description><![CDATA[Stories by Ruthu Rao on Medium]]></description>
        <link>https://medium.com/@ruthurao?source=rss-67efb3d458f2------2</link>
        <image>
            <url>https://cdn-images-1.medium.com/fit/c/150/150/0*86VoCw15jpEViFqJ</url>
            <title>Stories by Ruthu Rao on Medium</title>
            <link>https://medium.com/@ruthurao?source=rss-67efb3d458f2------2</link>
        </image>
        <generator>Medium</generator>
        <lastBuildDate>Sun, 22 Nov 2026 01:57:06 GMT</lastBuildDate>
        <atom:link href="https://medium.com/@ruthurao/feed" rel="self" type="application/rss+xml"/>
        <webMaster><![CDATA[yourfriends@medium.com]]></webMaster>
        <atom:link href="http://medium.superfeedr.com/" rel="hub"/>
        <item>
            <title><![CDATA[Building a Computer From Scratch: Understanding Memory #3]]></title>
            <link>https://medium.com/@ruthurao/building-a-computer-from-scratch-understanding-memory-3-46482c321e7d?source=rss-67efb3d458f2------2</link>
            <guid isPermaLink="false">https://medium.com/p/46482c321e7d</guid>
            <dc:creator><![CDATA[Ruthu Rao]]></dc:creator>
            <pubDate>Sun, 02 Feb 2025 15:00:50 GMT</pubDate>
            <atom:updated>2025-02-02T15:00:50.480Z</atom:updated>
            <content:encoded><![CDATA[<p>In the previous <a href="https://medium.com/@ruthurao/building-a-computer-from-scratch-understanding-arithmetic-logic-unit-2-315ce860c972">section</a>, we discussed combinational chips, which generate outputs depending simply on current inputs. In this section, we will look at sequential chips, which contain outputs determined by both current inputs and the chip’s internal state. This internal state enables sequential chips to keep memory. Sequential chips, unlike combinational chips, can store information over time.</p><p>Computers require memory elements that can retain data over time to store and recall values, in addition to computation. These memory elements are built using sequential chips. Memory implementation is an intricate art involving synchronization, clocking, and feedback loops.</p><p>Flip-flops, which are low-level sequential gates, can handle most of this complexity. Using flip-flops as building blocks, we will design and construct several memory devices used in modern computers, including binary cells, registers, memory banks, and counters.</p><p>In the context of digital circuits, “remembering something” refers to a process that is directly linked to time. In computers, memory is used not only to store data but also to retain and retrieve it over time. To create circuits that can “remember” information, we need to represent the passage of time, which is where the clock comes in.</p><p>When we consider combinational chips during an operation of x + y, x would be stored in register whereas y would be stored in far away RAM, in a combinational chip it doesn’t wait until the inputs have been received at the ALU, it operates even when its unstable, this is why DFFs in sequential chips is necessary as it introduces time delay and The output of the ALU (combinational chip) is eventually routed to a sequential chip,</p><p>The sequential chip updates its state only at the start of the next clock cycle, which ensures that any intermediate or “garbage” outputs from the ALU during the current clock cycle are ignored.</p><p>To ensure the system functions correctly, the clock cycle must be slightly longer than the time it takes for signals to travel the longest distance between chips in the system (e.g., from RAM to ALU). By the time the next clock cycle begins, the inputs to the sequential chip (coming from the ALU) will have stabilized, and the correct value will be stored.</p><p><strong>The Clock</strong></p><p>Most computers portray the passage of time with a master clock, which is a device that creates a continuous stream of alternating signals. This clock signal is often generated by an oscillator that alternates between two phases: zero and one, low and high, or tick and tock.</p><p>A clock cycle is the time interval between the start of one tick and the end of the next one, and each cycle represents one discrete unit of time in the computer.</p><p>The current clock phase is specified by a binary signal that is transmitted to all sequential chips in the computer. This synchronization ensures that all system components work together to process and transport data reliably and effectively.</p><p><strong>Flip-Flops</strong></p><p>Flip-flops are required for accessing and storing data in digital circuits over time. Among the different forms of flip-flops discussed below</p><pre>/**<br> * Flip-Flop Type    Inputs     Outputs     What it does?<br> * ----------------------------------------------------<br> * SR                S, R       Q, ~Q       Sets or resets the output based on S and R inputs.<br> * JK                J, K       Q, ~Q       Toggles output when both J and K are high; otherwise, sets or resets based on J and K.<br> * T                 T          Q, ~Q       Toggles output when T is high.<br> * D                 D, CLK     Q, ~Q       Captures and holds the input value on the clock edge.<br> * Master-Slave      Varies     Q, ~Q       Uses two stages to ensure stable and accurate state changes.<br> */<br></pre><p>We will discuss the Data Flip-Flop (DFF), which is fundamental because of its simple yet effective interface, consisting of:</p><ul><li>Single-bit data input: This is the value that the flip-flop will store.</li><li>Single-bit Data Output: This is the value currently stored in the flip-flop.</li><li>Clock Input: This signal varies continually in response to the master clock signal.</li></ul><p>The clock signal governs how a DFF operates. Specifically, the DFF adjusts its output to match the input value from the preceding clock cycle. This behavior is formally defined by the following equation:</p><p><em>Out (𝑡) = in (𝑡 — 1)</em></p><p>The gate’s input and output values are represented by in and out, respectively, while the current clock cycle is denoted by t. This means that at any given time, the DFF returns the value it got one clock cycle earlier. This simple but effective approach enables the DFF to “remember” the input value from the preceding time unit.</p><pre> <br>                ┌────────┐<br>in ────────────▶│  DFF   │──────▶ out<br>                └────────┘<br>              Out(t)= In(t-1)</pre><p><strong>Registers</strong></p><p>A register is a primitive storage device in digital systems that is capable of “remembering” a value over time. This capability is frequently described as the classical storage behavior:</p><p><em>Out(t)=Out(t−1)</em></p><p>In contrast, a data flip-flop (DFF) works on the following principle:</p><p><em>Out(t) = In(t-1)</em></p><p>This distinction emphasizes that, whereas a DFF can output its previous input, a register must be able to retain its output until expressly modified.</p><pre>  ___________________________________________<br>  |                 ┌────────┐              |<br>  |in ──────*──────▶│  DFF   │────*──▶ out  |<br>  |         |       └────────┘    |         |<br>  |         |                     |         |<br>  |         |_____________________|         |<br>  |_________________________________________|<br>              Out(t)= In(t-1)?<br>              In(t)= Out(t-1)?<br></pre><p>In digital systems, a D flip-flop (DFF) is used to hold a single bit of data. It has both an input (in) and an output. However, there is some uncertainty in the figure regarding how to tell the DFF to preserve its current value or update it with a new one (?)</p><p>There is no straightforward way to determine whether the DFF must “listen” to the new data coming from the <em>In</em> wire or retain the current value from the <em>Out</em> wire.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/320/0*qlTvo0KmCPcksttt.png" /><figcaption>1-bit register</figcaption></figure><p>To address this issue, a multiplexor is added. A multiplexor (MUX) is a device that selects one of several input signals based on a control signal.<br>The multiplexor’s control signal, known as the load bit, determines whether the register should store new data or retain the existing value.</p><ul><li>If the load bit is 1, the multiplexor chooses the input signal (new data) and transmits it to the DFF, where it is stored.</li><li>If the load bit is set to 0, the multiplexor returns the DFF’s current output to itself, ensuring that the value remains constant.</li></ul><p>A register is a storage unit for data. Initially, we deal with single-bit registers (which store only one bit, either 0 or 1).<br>To store advanced data, such as a number with multiple bits, we must create multi-bit registers.</p><p>A multi-bit register is created by stacking many single-bit registers. For example, a 32-bit register is made up of 32 single-bit registers that are lined up side by side. The “width” of a register indicates how many bits it can carry. A 16-bit, 32-bit, or 64-bit register can each hold 16, 32, or 64 bits.</p><p><strong>Memory</strong></p><p>In a RAM( Random Access Memory) chip, each word (or register) is allocated a unique address. The address determines the memory location to access during read/write operations.<br>For example, if a RAM chip has 100 registers, they are numbered 0–99. If we want to access register number 10, we use its address, which is 10.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/262/0*nN5DOUg9sRwTkjx6.png" /><figcaption>stacking together many registers to form a Random Access Memory (RAM) unit</figcaption></figure><p>A basic RAM device has three primary inputs:</p><ul><li>Data input represents the value (multi-bit word) that we wish to save in memory.</li><li>Address input indicates which register (or word) in RAM should be accessed.</li><li>The load bit decides whether we’re reading from or writing to memory.<br> ** Load = 0 (Read operation): The RAM retrieves and returns the value stored at the specified address.<br>** Load = 1 (Write operation): The RAM writes the input value into the register at the specified address.</li></ul><p><strong>Counters</strong></p><p>In digital systems, we required a mechanism to track sequences of instructions or events throughout time, which necessitated devices that remembered and updated specified values. <br>Combining registers and combinational logic allowed the development of more complicated sequential devices, such as Counters. This resulted in not only the storage of values but also actions that rely on those values, such as incrementing them.</p><p>Counters are used in various other digital systems to perform functions such as counting clock cycles, managing loops, tracking events, and program counters in CPUs, which control the execution flow of programs and keep track of the next instruction.</p><p>A counter is a digital circuit and sequential chip that produces an integer value normally increased by a constant (usually one) at regular intervals (every clock cycle). Its typical behavior is to increment by one per clock cycle, allowing the processor to acquire the next instruction.</p><p>However, there are situations in which flexibility is essential. The counter’s output changes depending on the preceding output, and it follows the rule:</p><p>Out (𝑡) = Out (𝑡 — 1) + 𝑐.</p><p>Where:</p><ul><li><em>Out(t)</em> represents the counter’s output at time <em>t</em>.</li><li><em>Out(t-1)</em> represents the counter’s output from the preceding time unit.</li><li><em>C</em> is a constant increment, generally one.</li></ul><p>As a result, most systems have a loadable and resettable counter. Control bits can be used to specify the functionality:</p><p>A reset bit to reset the counter to zero assuming that that’s the address of the program’s first instruction and when<em> inc</em> = <em>1</em> it is <em>Out(t)= Out (t-1)+1</em>, an increment bit (inc) to increment the counter once every clock cycle, and if we want to initialize it to some other counting base <em>d</em>, we put <em>d</em> in the in input and assert the load bit to initialize the counter to a certain value <em>d.</em></p><p>Overview of how the counter works</p><p><strong>Reset Signal</strong>(reset): Forces the counter to output zero, overriding all other inputs and halting all increases.<br><strong>Load Signal</strong>(load): Sets the counter’s output to the value of the input signal (in), independent of its prior state.<br><strong>Increment Signal</strong>(inc): When asserted, the counter’s output is incremented by 1 per clock cycle. When de-asserted, the incrementing process comes to a halt.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*UK9CqqP1Rsj2ygRs-pEiKQ.png" /></figure><p>We assume that we start tracking the counter in time unit 22, when its input and output are 527 and 47, respectively. We also assume that the counter’s control bits (reset, load, inc) start at 0-all arbitrary assumptions.</p><ul><li>Time 22–23:<br>Reset Signal: At time 23, the <em>reset signal </em>is asserted (reset = 1), triggering the counter to reset its output to 0.<br>Output: The output becomes 0 and remains 0 until another signal changes its state.</li><li>Time 24–25:<br>At time 25, the <em>increment signal</em> is asserted (inc = 1), allowing the counter to increment its output.<br>Output: The counter begins incrementing from 0 with the next clock cycle (time 26).</li><li>Time 26–29:<br>Continual Increment: As long as the <em>increment signal</em> is asserted (inc = 1), the counter will increment by one in each clock cycle.<br>At time 26, the output is 1.<br>At time 27, the output changes to 2.<br>The output continues to increase, reaching 4 at time 29.</li><li>Time 29–30:<br><em>Load Signal</em>: At time 29, the <em>load signal </em>is asserted (load = 1), resulting in the counter’s output matching the value of the input signal (in).<br>The current input (in) value is 527.<br>Output: The counter’s output is set to 527 at the next clock cycle (time 30).</li><li>Time 30–33:<br>Increment Resumes: Because the <em>increment signal</em> is still asserted (inc = 1), the counter resumes incrementing from 527.<br>At time 31, output reaches 528.<br>At time 32, output reaches 529.<br>At time 33, output reaches 530.</li><li>Time 33–34:<br>Stop Incrementing: At time 33, the <em>increment signal </em>is de-asserted (inc = 0), causing the counter to stop increasing.<br>Output: The output is stable at 530 and does not change further.</li></ul><p>In this chapter, we dealt with how sequential chips, involving flip-flops, registers, and counters, are the elementary building blocks of computer memory in which information is stored and treated successively.</p><p>While a combinational chip produces its output instantly, a sequential chip adds state and timing through clocked circuits, permitting the memory to be stable.</p><p>The D-Flip Flop (DFF) has a time delay at its core, which makes the operations synchronize and prevents unstable outputs. Registers further extend the concept to offer selective data storage, while counters enable sequential updating, which finds its application in operations related to tracking, such as instruction execution in a CPU.</p><p>These collectively form strong memory structures, including RAM, for the efficient storage and retrieval of data efficiently.</p><p>An understanding of these fundamental principles of memory provides a base for implementing some registers, memory units, and advanced storage architecture in the next chapter.</p><p>To see how Arithmetic Logic Unit (ALU), multiplexers, and other logic gates are used in practice, please read <a href="https://medium.com/@ruthurao/building-a-computer-from-scratch-understanding-computer-architecture-325e1d3e1f2c">Part 1</a> and <a href="https://medium.com/@ruthurao/building-a-computer-from-scratch-understanding-arithmetic-logic-unit-2-315ce860c972">Part 2</a> of this blog series. Stay tuned for the next blog.</p><p>You have reached the end of this blog, and thank you for reading! :)</p><img src="https://medium.com/_/stat?event=post.clientViewed&referrerSource=full_rss&postId=46482c321e7d" width="1" height="1" alt="">]]></content:encoded>
        </item>
        <item>
            <title><![CDATA[Building a Computer From Scratch: Understanding Arithmetic Logic Unit #2]]></title>
            <link>https://medium.com/@ruthurao/building-a-computer-from-scratch-understanding-arithmetic-logic-unit-2-315ce860c972?source=rss-67efb3d458f2------2</link>
            <guid isPermaLink="false">https://medium.com/p/315ce860c972</guid>
            <dc:creator><![CDATA[Ruthu Rao]]></dc:creator>
            <pubDate>Mon, 17 Jun 2024 14:33:44 GMT</pubDate>
            <atom:updated>2024-06-17T14:33:44.925Z</atom:updated>
            <content:encoded><![CDATA[<p>In my previous article, we looked at logic gates and their significance as the basic building blocks of digital circuits. These primitive gates, such as AND, OR, and NOT, use transistors in specific combinations to perform basic logical operations. Today, we’ll delve deeper into the world of digital computation by learning how to represent and add signed numbers, as well as understand and implement an Arithmetic Logic Unit (ALU).</p><p>Before we get into the complexities of an ALU, it’s critical to understand the key concepts of Boolean codes and Boolean arithmetic. Understanding these ideas is vital because they lay the groundwork for working with signed numbers, which eventually leads to the creation and functioning of an ALU. Binary addition, while seeming simple, is an essential function that underpins many of the activities performed by digital computers. Remarkably, most of the operations performed by digital computers can be reduced to elementary additions of binary numbers. As a result, a thorough understanding of binary addition is required, as it forms the foundation for many computations in computers.<br>In this part of our journey, we will discover the mechanics underlying binary addition, analyse how signed numbers are represented and manipulated, and result in the construction of a fully functional Arithmetic Logic Unit.</p><p>Binary addition has progressed greatly since the beginning, with multiple approaches devised to address various issues and increase efficiency.</p><ol><li><strong>Direct Binary Addition</strong>:</li></ol><ul><li>At first, binary addition was performed directly, much like decimal addition, but with binary digits (bits). This requires adding the appropriate bits from each number and carrying any overflow to the next higher bit position.</li></ul><p><strong>Binary Addition Without Overflow:</strong></p><pre>0101  (5 in decimal)<br>+ 0011  (3 in decimal)<br>------<br>  1000  (8 in decimal)</pre><p><strong>Binary Addition With Overflow:</strong></p><pre>1011  (11 in decimal)<br>+ 1101  (13 in decimal)<br>------<br> 11000  (24 in decimal, 5 bits including the overflow)</pre><p>The ‘1’ on the far left is the overflow carry bit.</p><p>2. <strong>1’s Complement:</strong></p><ul><li>1’s complement is a method of representing negative numbers in a binary form. In this system, a negative number is represented by reversing all of the bits of its positive equivalent (converting 1s to 0s and vice versa).</li><li>Binary addition with 1’s complement involves adding the numbers normally followed by any carry-out from the most significant bit to the least important bit (an end-around carry).</li></ul><p><strong>Adding -6 and 3 using 1’s complement</strong></p><ol><li>Represent the numbers in binary (4-bit representation for simplicity):</li></ol><ul><li>+6 in binary: 0110</li><li>-6 in 1’s complement: 1001 (invert all bits of 0110)</li><li>+3 in binary: 0011</li></ul><p>Add the numbers:</p><pre>1001  (-6 in 1&#39;s complement)<br> + 0011  (3 in binary)<br> ------<br>  1100</pre><p>No end-around carry is required.</p><p>If there was a carry, it would be added to the least significant bit:</p><pre>1010  (-5 in 1&#39;s complement)<br>+ 0111  (7 in binary)<br> ------<br>  10001  (Result with carry)<br>+    1  (Add the carry to the LSB)<br> ------<br>  0010  (Result after end-around carry adjustment)</pre><p>The result is 2 in decimal, indicating the correct sum of -5 and 7.</p><p>A challenge with 1’s complement is that it represents positive and negative numbers differently, further complicating the process of performing complex arithmetic operations. This resulted in the adoption of 2’s complement, that tackles the restrictions of 1’s complement.</p><p>3. <strong>2’s Compliment</strong></p><p>Represent the numbers in binary (4-bit representation for simplicity):</p><ul><li>+5 in binary: 0101</li><li>-5 in 2’s complement: 1011 (invert all bits of 0101 to get 1010, then add 1 to get 1011)</li><li>+7 in binary: 0111</li></ul><p>Add the numbers:</p><pre>1011  (-5 in 2&#39;s complement)<br> + 0111  (7 in binary)<br> ------<br>  0010  (Result is 2 in decimal)</pre><p>No end-around carry is needed in 2’s complement. The result directly represents the correct sum.</p><p>A negative number in 2’s complement is represented by inverting all of the bits from its positive counterpart and adding 1 to the least significant bit. The primary benefit of 2’s complement is its distinct representation for zero, which simplifies the hardware for addition and subtraction. This facilitates the addition of any two signed numbers without requiring special hardware beyond that needed for simple bit-wise addition.</p><p>The 2’s complement approach simplifies subtraction by negating a signed integer <em>x</em>’s bits and adding one, reducing hardware complexity. As a result, the equation <em>x-y = x + (-y)</em> simplifies subtraction. This suggests a single chip, the Arithmetic Logical Unit (ALU), can incorporate all fundamental arithmetic and logical operations in hardware, starting with an adder chip.</p><p>We present a hierarchy of three adders, leading to a multi-bit adder chip:</p><ul><li>Half-adder: designed to add two bits</li><li>Full-adder: designed to add three bits</li><li>Adder: designed to add two n-bit numbers</li></ul><h4>Half Adder</h4><p>The half adder is the simplest type of adder circuit. It can add two single-bit binary values and return a sum and carry.</p><ul><li><strong>Inputs</strong>: Two single bits.</li><li><strong>Outputs</strong>: Sum and Carry.</li><li><strong>Logic</strong>: The sum is computed using an XOR gate, and the carry is computed using an AND gate.</li></ul><figure><img alt="" src="https://cdn-images-1.medium.com/max/750/0*4Tnln8Z0YEptXAfl.png" /></figure><blockquote>HDL Representation of half-adder :</blockquote><pre><br>/**<br> * Computes the sum of two bits.<br> *<br> * Truth Table for Half Adder:<br> * <br> * | `a` | `b` | `sum` (a XOR b) | `carry` (a AND b) |<br> * |-----|-----|-----------------|------------------|<br> * |  0  |  0  |        0        |        0         |<br> * |  1  |  0  |        1        |        0         |<br> * |  0  |  1  |        1        |        0         |<br> * |  1  |  1  |        0        |        1         |<br> */<br> // adds two single-bit binary numbers<br>CHIP HalfAdder {<br>    IN a, b;    // 1-bit inputs<br>    OUT sum,    // Right bit of a + b <br>        carry;  // Left bit of a + b<br><br>    PARTS:<br>    // XOR gate for the sum<br>    //handles the addition of two bits without carrying over<br>    Xor(a=a, b=b, out=sum);<br>    // AND gate for the carry<br>    // handles the concept of carrying in binary addition<br>    And(a=a, b=b, out=carry);<br>}</pre><h4>Full Adder</h4><p>A full adder enhances the capability of a half adder by having an extra carry-in bit, allowing it to handle multi-bit binary addition more effectively.</p><ul><li><strong>Inputs</strong>: Two single bits and a carry-in bit.</li><li><strong>Outputs</strong>: Sum and Carry-out.</li><li><strong>Logic</strong>: The sum is computed using an XOR gate with the inputs and carry-in, whereas the carry-out is computed using a mixture of AND and OR gates.</li></ul><figure><img alt="" src="https://cdn-images-1.medium.com/max/750/0*PMrYbELQUj6Kt1vH.png" /></figure><blockquote>HDL Representation of full-adder:</blockquote><pre><br>/**<br> * Computes the sum of three bits.<br> *<br> * Truth Table for Full Adder:<br> * <br> * | `a` | `b` | `c` | `sum` (a XOR b XOR c) | `carry` (majority of a, b, c) |<br> * |-----|-----|-----|-----------------------|-------------------------------|<br> * |  0  |  0  |  0  |           0           |               0               |<br> * |  0  |  0  |  1  |           1           |               0               |<br> * |  0  |  1  |  0  |           1           |               0               |<br> * |  0  |  1  |  1  |           0           |               1               |<br> * |  1  |  0  |  0  |           1           |               0               |<br> * |  1  |  0  |  1  |           0           |               1               |<br> * |  1  |  1  |  0  |           0           |               1               |<br> * |  1  |  1  |  1  |           1           |               1               |<br> */<br> //  Uses two Half Adders and one OR gate to compute the sum and carry of three input bits<br>CHIP FullAdder {<br>    IN a, b, c;  // 1-bit inputs<br>    OUT sum,     // Right bit of a + b + c<br>        carry;   // Left bit of a + b + c<br><br>    PARTS:<br>    // First Half Adder: Add a and b<br>    HalfAdder(a=a, b=b, sum=abSum, carry=abCarry);<br><br>    // Second Half Adder: Add abSum and c<br>    HalfAdder(a=abSum, b=c, sum=sum, carry=bcCarry);<br><br>    // OR gate to combine the carry outputs<br>    // Combines the two intermediate carries (abCarry and bcCarry) to produce the final carry (carry).<br>    Or(a=abCarry, b=bcCarry, out=carry);<br>}</pre><h4>Adder</h4><p>Memory and register chips use n-bit patterns to represent integer values, n being 16, 32, 64, and so on (depending on the computer platform). The chip that adds such numbers is known as a multibit adder, or simply adder. The usage of n-bit patterns in memory and register chips to represent integer values is vital in modern digital computing. It enables flexible memory addressing, efficient binary arithmetic operations, and compatibility. Let’s take an example of a 16-bit adder to better understand this, as the same logic and specifications scale up to any n-bit adder.</p><h3>Add16–16-bit Adder</h3><ul><li><strong>Inputs:</strong> Two 16-bit data inputs, a[16] and b[16].</li><li><strong>Outputs:</strong>out[16]: The 16-bit sum of a and b.</li><li><strong>Logic: </strong>The sum is computed using integer 2’s complement addition where out = a + b. A series of full adders are used to add each corresponding bit of the 16-bit input arrays a and b. Overflow is neither detected nor handled.</li></ul><pre><br>                                ┌────────┐<br>             a[16] ────────────▶│16-bit  │<br>             b[16] ────────────▶│Adder   │                                <br>                                └────────┘</pre><blockquote>HDL Representation of a 16-bit-Adder:</blockquote><pre><br>/**<br> * 16-bit adder: Adds two 16-bit two&#39;s complement values.<br> * The most significant carry bit is ignored.<br> */<br>CHIP Add16 {<br>    IN a[16], b[16];<br>    OUT out[16];<br><br>    PARTS:<br>    // Use HalfAdder for the least significant bit because the addition <br>    // of the least significant bit does not involve any carry-in from a previous bit.<br>    HalfAdder(a=a[0], b=b[0], sum=out[0], carry=c0);<br><br>    // Use FullAdders for the remaining bits<br>    // Series of Full Adders to add each corresponding bit of the 16-bit input arrays a and b<br>    FullAdder(a=a[1], b=b[1], c=c0, sum=out[1], carry=c1);<br>    FullAdder(a=a[2], b=b[2], c=c1, sum=out[2], carry=c2);<br>    FullAdder(a=a[3], b=b[3], c=c2, sum=out[3], carry=c3);<br>    FullAdder(a=a[4], b=b[4], c=c3, sum=out[4], carry=c4);<br>    FullAdder(a=a[5], b=b[5], c=c4, sum=out[5], carry=c5);<br>    FullAdder(a=a[6], b=b[6], c=c5, sum=out[6], carry=c6);<br>    FullAdder(a=a[7], b=b[7], c=c6, sum=out[7], carry=c7);<br>    FullAdder(a=a[8], b=b[8], c=c7, sum=out[8], carry=c8);<br>    FullAdder(a=a[9], b=b[9], c=c8, sum=out[9], carry=c9);<br>    FullAdder(a=a[10], b=b[10], c=c9, sum=out[10], carry=c10);<br>    FullAdder(a=a[11], b=b[11], c=c10, sum=out[11], carry=c11);<br>    FullAdder(a=a[12], b=b[12], c=c11, sum=out[12], carry=c12);<br>    FullAdder(a=a[13], b=b[13], c=c12, sum=out[13], carry=c13);<br>    FullAdder(a=a[14], b=b[14], c=c13, sum=out[14], carry=c14);<br>    FullAdder(a=a[15], b=b[15], c=c14, sum=out[15]);<br>}</pre><h4>Incrementer</h4><p>It is a digital circuit that adds one to the input value. A 16-bit incrementer accepts a 16-bit binary number as input and returns the input value plus one as output. It is convenient to have a special-purpose chip dedicated to adding the constant 1 to a given number.</p><ul><li><strong>Inputs:</strong> One 16-bit data input, in[16].</li><li><strong>Outputs:</strong>out[16]: The 16-bit output, which is in + 1.</li></ul><pre> <br>                    ┌────────┐<br>in[16] ────────────▶│increm  │──────▶ out[16]<br>                    │enter   │ in + 1<br>                    └────────┘</pre><pre><br>/**<br> * 16-bit incrementer:<br> * out = in + 1<br> */<br>CHIP Inc16 {<br>    IN in[16];<br>    OUT out[16];<br><br>    PARTS:<br>    // Half Adder for the least significant bit (in[0]) to handle the increment by 1<br>    HalfAdder(a=in[0], b=true, sum=out[0], carry=carry1);<br><br>    // Full Adders for the remaining bits<br>    // For the remaining 15 bits (in[1] through in[15]), we use FullAdders to continue the carry as we increment each bit.<br>    FullAdder(a=in[1], b=carry1, c=false, sum=out[1], carry=carry2);<br>    FullAdder(a=in[2], b=carry2, c=false, sum=out[2], carry=carry3);<br>    FullAdder(a=in[3], b=carry3, c=false, sum=out[3], carry=carry4);<br>    FullAdder(a=in[4], b=carry4, c=false, sum=out[4], carry=carry5);<br>    FullAdder(a=in[5], b=carry5, c=false, sum=out[5], carry=carry6);<br>    FullAdder(a=in[6], b=carry6, c=false, sum=out[6], carry=carry7);<br>    FullAdder(a=in[7], b=carry7, c=false, sum=out[7], carry=carry8);<br>    FullAdder(a=in[8], b=carry8, c=false, sum=out[8], carry=carry9);<br>    FullAdder(a=in[9], b=carry9, c=false, sum=out[9], carry=carry10);<br>    FullAdder(a=in[10], b=carry10, c=false, sum=out[10], carry=carry11);<br>    FullAdder(a=in[11], b=carry11, c=false, sum=out[11], carry=carry12);<br>    FullAdder(a=in[12], b=carry12, c=false, sum=out[12], carry=carry13);<br>    FullAdder(a=in[13], b=carry13, c=false, sum=out[13], carry=carry14);<br>    FullAdder(a=in[14], b=carry14, c=false, sum=out[14], carry=carry15);<br>    FullAdder(a=in[15], b=carry15, c=false, sum=out[15]);<br>}</pre><p>The previously stated adder chips were designed to be general, meaning they could be used in any computer system. Adders play an important part in the ALU by directly handling addition and subtraction operations. They also carry out complex instructions; Multipliers, shifters, and other logical units work together. To handle different data types and processes, the ALU includes numerous adders with varying bit widths. These circuits can handle carry bits, sign bits, and zero detection, which increases the ALU’s adaptability.</p><p>As mentioned earlier, we discussed how the Arithmetic Logic Unit (ALU) executes a preset set of operations. Now we’ll try to build a simple ALU for the Hack computer platform. Despite the platform-specific implementation, the core design ideas are widely applicable. The Hack ALU provides immense capability with a small number of internal components, exhibiting efficient and beautiful logic design.</p><h3>Behind the scenes of an ALU:</h3><ul><li><strong>Control Unit: </strong>In a computing system, the central processing unit (CPU) contains a control unit that interprets programme instructions. These instructions specify which operations the ALU must carry out and with what values.</li><li><strong>Instruction Set</strong>: The CPU’s instruction set defines the operations that an ALU can do. Each operation (such as addition, subtraction, and bitwise operations) is assigned a unique opcode (operation code) inside the instruction set.</li><li><strong>Programming and Compilation:</strong> When a programme is developed, it includes high-level commands (like x - 1mentioned below). During compilation, these commands are converted into machine code, which contains precise opcodes and operand specifications that instruct the control unit on how to configure the ALU.</li><li><strong>Execution:</strong> During code execution, the control unit reads these instructions and configures the ALU’s control signals accordingly. It loads the operands (x and y values) into registers or straight into the ALU, then sets the control bits (zx, nx, zy, ny, f, no) to the necessary values to complete the operation.</li></ul><p>In this example, we explore the operation of the Arithmetic Logic Unit (ALU), focusing on computing a specific set of functions <strong><em>out = f_i(x, y)</em></strong>, where <strong><em>x</em></strong> and <strong><em>y</em></strong> are 16-bit inputs, <strong><em>out</em></strong> is the 16-bit output, and <strong><em>f_i</em></strong> represents an arithmetic or logical function chosen from eighteen possibilities. The function <strong><em>f_i</em></strong> to compute is selected by configuring six control bits to specific binary values.</p><p>Each of the six control bits instructs the ALU to perform a specific elementary operation. When combined, these operations allow the ALU to perform a variety of useful functions. The ALU’s six control bits determine its behaviour, it has the capability to potentially compute 64 different functions (2^6 = 64).</p><p>The table below indicates the configuration for each set of control bits, as well as the action that the ALU performs based on those settings.</p><pre><br>if zx then x=0 <br>if nx then x = !x<br>if zy then y=0<br>if zy then y = !y<br>if f then out=x+y else out=x&amp;y<br>if no then out=!out         <br>      <br>| zx | nx | zy | ny | f | no | Resulting ALU output | <br>|                                 out = f(x,y)      |<br>|----|----|----|----|---|----|----------------------|<br>| 1  | 0  | 1  | 0  | 1 | 0  | 0                    | <br>| 1  | 1  | 1  | 1  | 1 | 1  | 1                    |<br>| 1  | 1  | 1  | 0  | 1 | 0  | -1                   |<br>| 0  | 0  | 1  | 1  | 0 | 0  | x                    |<br>| 1  | 1  | 0  | 0  | 0 | 0  | y                    |<br>| 0  | 0  | 1  | 1  | 0 | 1  | !x                   |<br>| 1  | 1  | 0  | 0  | 0 | 1  | !y                   |<br>| 0  | 0  | 1  | 1  | 1 | 1  | -x                   |<br>| 1  | 1  | 0  | 0  | 1 | 1  | -y                   |<br>| 0  | 1  | 1  | 1  | 1 | 1  | x+1                  |<br>| 1  | 1  | 0  | 1  | 1 | 1  | y+1                  | <br>| 0  | 0  | 1  | 1  | 1 | 0  | x-1                  |<br>| 1  | 1  | 0  | 0  | 1 | 0  | y-1                  |<br>| 0  | 0  | 0  | 0  | 1 | 0  | x+y                  | <br>| 0  | 1  | 0  | 0  | 1 | 1  | x-y                  |<br>| 0  | 0  | 0  | 1  | 1 | 1  | y-x                  |<br>| 0  | 0  | 0  | 0  | 0 | 0  | x&amp;y                  |<br>| 0  | 1  | 0  | 1  | 0 | 1  | x|y                  | </pre><blockquote>In the example below, the ALU computes the function <strong>x−1</strong>.</blockquote><pre>| zx | nx | zy | ny | f | no | Resulting ALU output | <br>|                                 out = f(x,y)      |<br>|----|----|----|----|---|----|----------------------|<br>| 0  | 0  | 1  | 1  | 1 | 0  | x-1                  |</pre><pre>Chip name: ALU<br>Inputs:<br>  x[16], Y[16];   // Two 16-bit data inputs<br>  zx,             // Zero the x input<br>  nx,             // Negate the x input<br>  zy,             // Zero the y input<br>  ny,             // Negate the y input<br>  f,              // Function code: 1 for Add, 0 for And<br>  no              // Negate the out output<br><br>Outputs:<br>  out[16],        // 16-bit output<br>  zr,             // True if out=0<br>  ng              // True if out&lt;0<br><br>Function:<br>  if zx then x = 0      // 16-bit zero constant<br>  if nx then x = !x     // Bit-wise negation<br>  if zy then y = 0      // 16-bit zero constant<br>  if ny then y = !y     // Bit-wise negation<br>  if f then out = x + y // Integer 2&#39;s complement addition<br>  else out = x &amp; y      // Bit-wise And<br>  if no then out = !out // Bit-wise negation<br>  if out=0 then zr = 1 else zr = 0  // 16-bit eq. comparison<br>  if out&lt;0 then ng = 1 else ng = 0  // 16-bit neg. comparison<br><br>Comment:<br>  Overflow is neither detected nor handled.</pre><ul><li><strong>No alteration to x</strong>: zx and nx are set to 0, keeping x unchanged as zx and nx changes only if it is true (1), it sets the x input to zero otherwise stays as it is.</li><li><strong>Setting y to -1</strong>: zy is set to 1 so it zeroes the y value, and ny is set to 1 so it negates the zero, producing -1.</li><li><strong>Addition selected</strong>: f is set to 1 to perform addition, resulting inx+(-1), which is effectively our function x-1.</li><li><strong>Output as</strong>: no is set to 0 to keep the output from the addition operation unchanged.</li></ul><blockquote>Here’s a simple implementation of an ALU</blockquote><pre>/**<br> * ALU (Arithmetic Logic Unit): fundamental component in a computer&#39;s CPU responsible for performing arithmetic and logical operations on binary data.<br> * Computes out = one of the following functions:<br> *                0, 1, -1,<br> *                x, y, !x, !y, -x, -y,<br> *                x + 1, y + 1, x - 1, y - 1,<br> *                x + y, x - y, y - x,<br> *                x &amp; y, x | y<br> * on the 16-bit inputs x, y,<br> * according to the input bits zx, nx, zy, ny, f, no.<br> * In addition, computes the two output bits:<br> * if (out == 0) zr = 1, else zr = 0<br> * if (out &lt; 0)  ng = 1, else ng = 0<br> */<br>// It takes two 16-bit inputs (x and y) and computes one of several functions specified by <br>// control bits (zx, nx, zy, ny, f, no).<br>// Implementation: Manipulates the x and y inputs<br>// and operates on the resulting values, as follows:<br>// if (zx == 1) sets x = 0        // 16-bit constant<br>// if (nx == 1) sets x = !x       // bitwise not<br>// if (zy == 1) sets y = 0        // 16-bit constant<br>// if (ny == 1) sets y = !y       // bitwise not<br>// if (f == 1)  sets out = x + y  // integer 2&#39;s complement addition<br>// if (f == 0)  sets out = x &amp; y  // bitwise and<br>// if (no == 1) sets out = !out   // bitwise not<br><br>CHIP ALU {<br>    IN  <br>        x[16], y[16],  // 16-bit inputs        <br>        zx, // zero the x input?<br>        nx, // negate the x input?<br>        zy, // zero the y input?<br>        ny, // negate the y input?<br>        f,  // compute (out = x + y) or (out = x &amp; y)?<br>        no; // negate the out output?<br>    OUT <br>        out[16], // 16-bit output<br>        zr,      // if (out == 0) equals 1, else 0<br>        ng;      // if (out &lt; 0)  equals 1, else 0<br><br>    PARTS:<br>    Mux16(a = x, b[0..15] = false, sel = zx, out = ozx); // If &#39;zx&#39; is 1, &#39;ozx&#39; is set to 0 (since &#39;b&#39; is all zeros). If &#39;zx&#39; is 0, &#39;ozx&#39; is set to &#39;x&#39;.<br>    Not16(in = ozx, out = onxb); // Bitwise negates &#39;ozx&#39; to produce &#39;onxb&#39;.<br>    Mux16(a = ozx, b = onxb, sel = nx, out = onx); // If &#39;nx&#39; is 1, &#39;onx&#39; is set to &#39;onxb&#39; (negated &#39;ozx&#39;). If &#39;nx&#39; is 0, &#39;onx&#39; is set to &#39;ozx&#39;.<br><br>    Mux16(a = y, b[0..15] = false, sel = zy, out = ozy); // If &#39;zy&#39; is 1, &#39;ozy&#39; is set to 0. If &#39;zy&#39; is 0, &#39;ozy&#39; is set to y.<br>    Not16(in = ozy, out = onyb); // Bitwise negates &#39;ozy&#39; to produce &#39;onyb&#39;.<br>    Mux16(a = ozy, b = onyb, sel = ny, out = ony); // If &#39;ny&#39; is 1, &#39;ony&#39; is set to &#39;onyb&#39; (negated &#39;ozy&#39;). If &#39;ny&#39; is 0, &#39;ony&#39; is set to &#39;ozy&#39;.<br><br>    And16(a = onx, b = ony, out = oaab); // Performs bitwise AND on &#39;onx&#39; and &#39;ony&#39; to produce &#39;oaab&#39;.<br>    Add16(a = onx, b = ony, out = oapb); // Performs addition on &#39;onx&#39; and &#39;ony&#39; to produce &#39;oapb&#39;.<br>    Mux16(a = oaab, b = oapb, sel = f, out = oab); //  If &#39;f&#39; is 1, &#39;oab&#39; is set to &#39;oapb&#39; (addition result). <br>    // If &#39;f&#39; is 0, &#39;oab&#39; is set to &#39;oaab&#39; (AND result).<br>    Not16(in = oab, out = noab); // Bitwise negates &#39;oab&#39; to produce &#39;noab&#39;.<br>    Mux16(a = oab, b = noab, sel = no, out = out, <br>          out[0..7] = f1, out[8..15] = f2,<br>          out[15] = ng); // If &#39;no&#39; is 1, &#39;out&#39; is set to &#39;noab&#39; (negated &#39;oab&#39;). <br>          // If &#39;no&#39; is 0, &#39;out&#39; is set to &#39;oab&#39;.<br>    Or8Way(in = f1, out = o1); // Computes OR for the first 8 bits of &#39;out&#39; to produce &#39;o1&#39;.<br>    Or8Way(in = f2, out = o2);// Computes OR for the next 8 bits of &#39;out&#39; to produce &#39;o2&#39;.<br>    Or(a = o1, b = o2, out = nzr);// Computes OR for &#39;o1&#39; and &#39;o2&#39; to produce nzr.<br>    Not(in = nzr, out = zr); // Negates &#39;nzr&#39; to produce &#39;zr&#39;. If all bits of &#39;out&#39; are 0, &#39;zr&#39; is set to 1, otherwise, it is set to 0.<br>}</pre><p>The ALU accepts two 16-bit binary inputs x and yand performs one of various operations on them using the control bits zx, nx, zy, ny, f, and no to specify the operation to be executed, resulting in a 16-bit output out based on two status flags: zr (zero flag) and ng(negative flag)to produce results for the above-mentioned functions.</p><p>To see how multiplexers and other logic gates are used in practice, please read <a href="https://medium.com/@ruthurao/building-a-computer-from-scratch-understanding-computer-architecture-325e1d3e1f2c">Part 1</a> of this blog series. You can check out the file on <a href="https://github.com/route-2/nand2tetris/blob/main/projects/2/ALU.tst">GitHub</a> for a more in-depth overview on implementation of the ALU( Outputs of each of the above implementations). It provides a rundown of how the arithmetic logic unit (ALU) processes inputs based on the specified control bits to produce the desired outputs.</p><p>You have reached the end of this blog, and thank you for reading! :)</p><img src="https://medium.com/_/stat?event=post.clientViewed&referrerSource=full_rss&postId=315ce860c972" width="1" height="1" alt="">]]></content:encoded>
        </item>
        <item>
            <title><![CDATA[Building a Computer From Scratch: Understanding Computer Architecture #1]]></title>
            <link>https://medium.com/@ruthurao/building-a-computer-from-scratch-understanding-computer-architecture-325e1d3e1f2c?source=rss-67efb3d458f2------2</link>
            <guid isPermaLink="false">https://medium.com/p/325e1d3e1f2c</guid>
            <category><![CDATA[computer-architecture]]></category>
            <category><![CDATA[logic-gates]]></category>
            <dc:creator><![CDATA[Ruthu Rao]]></dc:creator>
            <pubDate>Mon, 10 Jun 2024 08:15:19 GMT</pubDate>
            <atom:updated>2024-06-11T05:58:00.656Z</atom:updated>
            <content:encoded><![CDATA[<p>Throughout this blog series, we will embark on a thrilling adventure to construct a computer from scratch. We will utilise the software and hardware simulators provided by <a href="http://www.nand2tetris.org/">nand2tetris</a> alongside the informative guidebook, “The Elements of Computing Systems: Building a Modern Computer from First Principles.” Come join us as we look at the complicated interplay of hardware and software that drives modern computing by breaking it down into computer architecture. Let us begin by exploring the major abstractions that underpin the design of a typical computing system.</p><p><strong>The hierarchical design of computer systems</strong><br>Computer systems are built in layers, with each layer offering abstract services and building blocks for the layer above. This hierarchical technique reduces the complexities of computer design and development. Here’s a breakdown of these layers, from the most basic to the most abstract:</p><p>Digital Logic Level: This is where computer hardware gets its foundation. It all comes down to simple electronic circuits like multiplexers, flip-flops, and gates. They serve as the foundation for circuits that are more intricate.</p><p>Moving up a level, we have the microarchitecture. This is all about designing the processor and its components. We’re talking about things like the registers, Arithmetic Logic Unit (ALU), and control units. It’s all about figuring out how the CPU will actually execute instructions.</p><p>That being said, the Instruction Set Architecture (ISA). This is like the bridge between software and hardware. It lays out the specific set of instructions that a processor can execute, as well as how they’re represented in binary form.</p><p>Now, the Operating System Level. The operating system is used in that case. It offers services to the application software and oversees all hardware resources. In essence, it handles all the intricate details in the background, resulting in an intuitive software development interface.</p><p>At last , the Application Level is presented. Application software works with the operating system at its most advanced level to carry out particular functions for users. Everything from word processors to web browsers and gaming is included in this level.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*OX3nAKrakWxh1rKPXKWJ7g.png" /></figure><p>We frequently overlook the complex layers that function beneath the surface of a computer when we use one. We often consider it to be as simple as writing a programme that executes on a machine and completes our task. But actuality is much more complicated. To understand and carry out the instructions, the computer carefully breaks down the programme, reads the code, and converts it into binary form. The tiered mechanism that drives everything from binary execution to high-level code is what actually opens our daily computer experiences.</p><p>Machine language is just a collection of binary codes that everyone agrees on. It’s like an abstract idea that needs to be brought to life through hardware architecture. This architecture is then implemented using a specific chip set that contains registers, memory units, the ALU, and other useful components. Each of these hardware devices is comprised of a number of elementary logic gates. These gates can be constructed using fundamental gates such as NAND and NOR, which are made up of a collection of tiny switching devices, typically transistors. I won’t get into the nitty-gritty specifics because that’s where computer science meets physics, and things get pretty confusing.</p><p>As we get started on the adventure of creating a computer from scratch, we begin with the fundamental building blocks: logic gates. While we will not physically implement these gates, we will define their logical behaviour with Hardware Description Language (HDL). The logical behaviour of these gates is the same across all computers, independent of the materials or fabrication techniques utilised. This consistency originates from the basic laws of digital logic, which are unaffected by physical implementation.</p><p>To understand how to design logic gates, we must first grasp their function. Logic gates are physical devices that perform Boolean functions These Boolean functions are algebraic expressions derived from Boolean variables and operations. They define how output values are determined by input values and can be represented in truth tables that list all possible input combinations and their matching outputs. Boolean algebra is a mathematical framework used to analyse and develop logical systems.It works with binary variables, which can only have one of two values: true (1) or false(0). AND, OR, and NOT are the fundamental operations of Boolean algebra, establishing the framework for more complex equations and processes.</p><p>Boolean algebra helps to simplify computer circuit design by abstracting the intricate physical mechanisms of gates. This enables computer scientists to concentrate entirely on logic and functionality, rather than the finer points of physical implementation. Gates, the fundamental building blocks of digital circuits, use transistors grouped in precise configurations to carry out basic logical functions. The gates’ input pins accept binary data as inputs, and and outputs are derived from the results of the Boolean functions they implement.</p><p>Here are some simple logic gates.</p><ul><li><strong>OR Gate</strong>: Returns true if at least one of the inputs is true.</li><li><strong>AND Gate</strong>: Returns true when both inputs are true.</li><li><strong>NOT Gate</strong>: Returns the inverse of its input.</li><li><strong>NAND Gate</strong>: Returns false only if both inputs are true; effectively a NOT-AND.</li><li><strong>NOR Gate</strong>: Outputs true only when both inputs are false; essentially a NOT-OR.</li><li><strong>XOR Gate</strong>: Returns true when the inputs vary, crucial for comparison tasks.</li><li><strong>XNOR Gate</strong>: Also known as NOT-XOR, it produces a true output when the inputs are equal.</li></ul><p>Since all logic gates have the same input and output semantics (0’s and 1&#39;s), they can be chained together to create composite gates of varying complexity. Consider the 3-way Boolean function And(a, b, c). To use Boolean algebra, note that a·b·c = (a·b)·c. Alternatively, using prefix notation, And(a, b, c) = And(And(a, b), c).</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*YTsGQ0uKNXIECFwx6DLmQA.png" /></figure><p>Initially, hardware designers built gates physically, frequently combining AND, OR, and NOT gates to form more complicated ones such as XOR gates. However, correcting even minor flaws in physical structure proved difficult. Today, hardware designers use computer workstations to plan and optimise chip architecture. They employ structured modelling languages like Hardware Description Language (HDL), often known as VHDL (where V stands for Virtual), to simulate and refine designs virtually, removing the need for manual creation and making error correction simple.</p><p>A chip’s HDL specification is divided into two sections: header and components. The header section defines the chip’s interface, including its name and the names of its input and output pins. The parts section describes the names and arrangements of all of the lower-level components (other chips) utilised to build the chip. Each part is represented by a statement that includes the part name and its connections. When writing an HDL programme, make sure that you define your input and output pins. Inter-part connections are formed by creating and connecting internal pins as required.</p><p>Let’s go over the process of implementing an AND gate in the HDL program using a pre-set NAND gate from nand2tetris. Just like axioms in mathematics, primitive gates serve as the foundation for building more complex structures. These gates come with a ready-made implementation, allowing us to use them without concerning ourselves with their internal workings.</p><pre>/**<br> * And gate:<br> * if (a and b) out = 1, else out = 0 <br> */<br>CHIP And {<br>    IN a, b;    // Declare input pins a and b<br>    OUT out;    // Declare output pin out<br><br>    PARTS:<br>    // Using NAND to implement AND<br>    Nand(a=a, b=b, out=nandOut);  // First NAND operation with inputs a and b<br>    Nand(a=nandOut, b=nandOut, out=out);  // Negate the output of the first NAND<br>}</pre><p>This piece of code demonstrates the construction of an AND gate using HDL by combining NAND gates.</p><ul><li>Input and Output: The gate requires two inputs, labeled as a and b, and generates a single output, referred to as out.</li><li>First NAND Gate: It takes a and b as its inputs and produces an intermediate output known as nandOut. A NAND gate produces a true output only when at least one of its inputs is false.</li><li>Second NAND Gate: This gate takes nandOut as both of its inputs and inverts the signal. This effectively transforms the NAND gate into a NOT gate.</li></ul><p>By combining these two steps, the circuit functions as an AND gate. When both a and b are true, the output out is also true. If either or both inputs are false, the output will be false. This example illustrates how more intricate logic gates can be constructed using simpler ones.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*M2KeZFoTs_jit_b_q0X1FQ.png" /></figure><p>When I run this HDL code in the hardware simulator, it produces the following outputs for the AND gate:</p><pre>a=0, b=0 =&gt; out=0<br>a=0, b=1 =&gt; out=0<br>a=1, b=0 =&gt; out=0<br>a=1, b=1 =&gt; out=1</pre><p>This confirms that the AND gate is correctly implemented using NAND gates.</p><p>In a similar way, let’s explore how MUX and DMUX work, and delve into their implementations.</p><h4>Multiplexer (MUX)</h4><p>A multiplexer chooses one out of many input signals and sends it to a single output. It is a digital switch enabling several input signals to utilize one output line simultaneously. In essence, it picks one input from several and sends it to the output according to a selection signal.<br>Consider a MUX as a railway switch that guides the train (data) from multiple tracks (inputs) to one track (output) depending on a control mechanism (selection signal).<br><strong>How it works</strong></p><ul><li>Input: It usually has numerous inputs, typically denoted as a, b, c,…</li><li>Selection Signal: The selection signal (sel) determines which input is to be directed to the output.</li><li>Output: The output is a single line that carries the value of the selected input.</li></ul><p>For example , a 2-to-1 multiplexer has two inputs and one selection signal:</p><ul><li>When sel = 0, the output is the first input (a).</li><li>When sel = 1, the output is the second input (b).</li></ul><p>Here’s an HDL representation of 2-to-1 multiplexer:</p><pre>CHIP Mux {<br>    IN a, b, sel;<br>    OUT out;<br><br>    PARTS:<br>    // nSel = not sel<br>    Not(in=sel, out=nSel);<br><br>    // aAnd = a AND nSel<br>    And(a=a, b=nSel, out=aAnd);<br><br>    // bAnd = b AND sel<br>    And(a=b, b=sel, out=bAnd);<br><br>    // out = aAnd OR bAnd<br>    Or(a=aAnd, b=bAnd, out=out);<br>}</pre><p>Within this piece of code:<br>NOT gate is used to invert the selection signal sel.<br>Two AND gates direct the correct input to the output depending on the chosen signal.<br>OR gate merges these outputs to generate the ultimate result.</p><p>In the same way, we can create a MUX16, MUX4Way16, and MUX8Way16 by utilising fundamental MUX elements.</p><h4>MUX16</h4><p>A MUX16 is a 16-bit multiplexer that selects one of two 16-bit inputs based on a selection signal (sel) and produces a 16-bit output. When sel is 0, the output is equal to input a, and when sel is 1, the output is equal to input b.</p><pre>/**<br> * 16-bit multiplexor: <br> * selects one of two 16-bit inputs based on a selection signal &amp; produces a 16-bit output (out).<br> * when sel is 0, the output is equal to input a, and when sel is 1, the output is equal to input b<br> * for i = 0, ..., 15:<br> * if (sel = 0) out[i] = a[i], else out[i] = b[i]<br> */<br><br>CHIP Mux16 {<br>    IN a[16], b[16], sel;<br>    OUT out[16];<br><br>    PARTS:<br>    // Instantiate 16 2-input Mux chips to select between corresponding bits of a and b<br>    // according to the value of sel.<br>    Mux(a=a[0], b=b[0], sel=sel, out=out[0]);<br>    Mux(a=a[1], b=b[1], sel=sel, out=out[1]);<br>    Mux(a=a[2], b=b[2], sel=sel, out=out[2]);<br>    Mux(a=a[3], b=b[3], sel=sel, out=out[3]);<br>    Mux(a=a[4], b=b[4], sel=sel, out=out[4]);<br>    Mux(a=a[5], b=b[5], sel=sel, out=out[5]);<br>    Mux(a=a[6], b=b[6], sel=sel, out=out[6]);<br>    Mux(a=a[7], b=b[7], sel=sel, out=out[7]);<br>    Mux(a=a[8], b=b[8], sel=sel, out=out[8]);<br>    Mux(a=a[9], b=b[9], sel=sel, out=out[9]);<br>    Mux(a=a[10], b=b[10], sel=sel, out=out[10]);<br>    Mux(a=a[11], b=b[11], sel=sel, out=out[11]);<br>    Mux(a=a[12], b=b[12], sel=sel, out=out[12]);<br>    Mux(a=a[13], b=b[13], sel=sel, out=out[13]);<br>    Mux(a=a[14], b=b[14], sel=sel, out=out[14]);<br>    Mux(a=a[15], b=b[15], sel=sel, out=out[15]);<br>}</pre><h4>MUX4Way16</h4><p>A MUX4Way16 is a 4-way 16-bit multiplexer that selects one of four 16-bit inputs based on a 2-bit selection input. Here’s how we use MUX16 components to build a MUX4Way16:</p><pre>/**<br> * 4-way 16-bit multiplexor:<br> * out = a if sel = 00<br> *       b if sel = 01<br> *       c if sel = 10<br> *       d if sel = 11<br> * selects between four 16-bit inputs (a, b, c, d) based on a 2-bit selection input (sel)<br>*/<br><br><br>CHIP Mux4Way16 {<br>    IN a[16], b[16], c[16], d[16], sel[2];<br>    OUT out[16];<br>    <br>    PARTS:<br>  // Implementing two 2-way 16-bit multiplexers<br>    Mux16(a=a, b=b, sel=sel[0], out=temp1);<br>    Mux16(a=c, b=d, sel=sel[0], out=temp2);<br><br>    // Selecting the correct output based on the second bit of the selection input (sel[1])<br>    Mux16(a=temp1, b=temp2, sel=sel[1], out=out);<br>}</pre><p>In this code, we initially utilise two MUX16 components to choose between inputs a and b, and c and d, based on the first bit of the selection signal (sel[0]. The second bit of the selection signal is then used to select between the outputs of the first two MUX16 components.<br>Using these fundamental components, we can build more complex multiplexers, such as MUX8Way16, by combining MUX4Way16 and MUX16 elements.</p><h4>Demultiplexer (DMUX)</h4><p>A demultiplexer, or DMUX, serves the opposite function to a multiplexer. It accepts a single input and assigns it to one of numerous output lines based on a selection signal.<br>Consider a DMUX to be a distribution switch that directs a single data signal (input) to one of numerous output lines using a control mechanism (selection signal).</p><p>How It Works</p><ul><li><strong>Input</strong>: A demultiplexer has a single input.</li><li><strong>Selection Signal</strong>: The selection signal (sel) determines which output the input should be routed to.</li><li><strong>Outputs</strong>: The outputs are multiple lines that can carry the input value.</li></ul><p>For example, a 1-to-2 demultiplexer has one input and one selection signal:</p><ul><li>When sel = 0, the input is routed to the first output (a).</li><li>When sel = 1, the input is routed to the second output (b).</li></ul><p>Here is an HDL implementation of a 1-to-2 demultiplexer:</p><pre>/**<br> * Demultiplexor takes a single input signal and routes it to one of two output signals based on the selection signal (sel).<br> * [a, b] = [in, 0] if sel = 0<br> *          [0, in] if sel = 1<br> */<br>CHIP DMux {<br>    IN in, sel;<br>    OUT a, b;<br><br>    PARTS:<br>     // NOT gate to invert the selection signal<br>    Not(in=sel, out=nsel);<br><br>    // AND gates to route the input to the correct output based on the selection signal<br>    And(a=in, b=nsel, out=a);<br>    And(a=in, b=sel, out=b);<br>}</pre><p>In this code:</p><ul><li>The selection signal sel is inverted using a NOT gate.</li><li>Two AND gates route the input to the appropriate output based on the selection signal.</li></ul><p>Using the basic DMux, we can build more complicated demultiplexers like DMux4Way and DMux8Way.</p><h4>DMux4Way</h4><p>A 4-way demultiplexer takes a single input signal and routes it to one of four outputs based on a 2-bit selection signal.</p><h4>How it works:</h4><p>The DMux4Way behaves as follows:</p><ul><li>When sel is 00, the input is routed to a.</li><li>When sel is 01, the input is routed to b.</li><li>When sel is 10, the input is routed to c.</li><li>When sel is 11, the input is routed to d.</li></ul><p>Here’s the HDL implementation of a 4-way demultiplexor:</p><pre>/**<br> * 4-way demultiplexor demultiplexer takes a single input signal and routes it to one of four output signals based on a 2-bit selection signal (sel).<br> * [a, b, c, d] = [in, 0, 0, 0] if sel = 00<br> *                [0, in, 0, 0] if sel = 01<br> *                [0, 0, in, 0] if sel = 10<br> *                [0, 0, 0, in] if sel = 11<br> */<br>CHIP DMux4Way {<br>    IN in, sel[2];<br>    OUT a, b, c, d;<br><br>    PARTS:<br>   // First level DMux splits the input based on sel[1] (MSB) into two intermediate signals (ab and cd)<br>    DMux(in=in, sel=sel[1], a=ab, b=cd);<br>    <br>    // Second level DMux further splits into outputs a and b based on the LSB of sel (sel[0]).<br>    DMux(in=ab, sel=sel[0], a=a, b=b);<br>    <br>    // Second level DMux further splits into outputs c and d based on the LSB of sel (sel[0]).<br>    DMux(in=cd, sel=sel[0], a=c, b=d);<br>   <br>}</pre><p>In this code:</p><ul><li>We use a DMux to split the input in into two intermediate signals, ab and cd, based on the most significant bit (sel[1]) of the selection signal.</li><li>We further split ab into a and b based on the least significant bit (sel[0]) of the selection signal.</li><li>Similarly, we split cd into c and d based on the least significant bit (sel[0]) of the selection signal.</li></ul><h3>DMux8Way</h3><p>An 8-way demultiplexer takes a single input signal and routes it to one of eight outputs based on a 3-bit selection signal.</p><h4>How it works:</h4><p>The DMux8Way behaves as follows:</p><ul><li>When sel is 000, the input is routed to a.</li><li>When sel is 001, the input is routed to b.</li><li>When sel is 010, the input is routed to c.</li><li>When sel is 011, the input is routed to d.</li><li>When sel is 100, the input is routed to e.</li><li>When sel is 101, the input is routed to f.</li><li>When sel is 110, the input is routed to g.</li><li>When sel is 111, the input is routed to h.</li></ul><p>Here’s the HDL implementation of a 8-way demultiplexor:</p><pre>/**<br> * 8-way demultiplexor takes a single input signal and routes it to one of eight possible output signals based on a 3-bit selection signal (sel).<br> * [a, b, c, d, e, f, g, h] = [in, 0,  0,  0,  0,  0,  0,  0] if sel = 000<br> *                            [0, in,  0,  0,  0,  0,  0,  0] if sel = 001<br> *                            [0,  0, in,  0,  0,  0,  0,  0] if sel = 010<br> *                            [0,  0,  0, in,  0,  0,  0,  0] if sel = 011<br> *                            [0,  0,  0,  0, in,  0,  0,  0] if sel = 100<br> *                            [0,  0,  0,  0,  0, in,  0,  0] if sel = 101<br> *                            [0,  0,  0,  0,  0,  0, in,  0] if sel = 110<br> *                            [0,  0,  0,  0,  0,  0,  0, in] if sel = 111<br> */<br>  CHIP DMux8Way {<br>    IN in, sel[3];<br>    OUT a, b, c, d, e, f, g, h;<br><br>    PARTS:<br>    // First level of demultiplexing based on the most significant bit (sel[2])<br>    //splits &#39;in&#39; into four signals based on the two most significant bits of &#39;sel&#39;<br>    DMux4Way(in=in, sel=sel[1..2], a=w,b=x,c=y,d=z);<br>    <br>    // Further demultiplexing based on the remaining bits sel[0]<br>    // Each of the four signals from the first level is further demultiplexed into two signals<br>    // based on the least significant bit of &#39;sel&#39;<br>    DMux(in=w, sel=sel[0], a=a, b=b);<br>    DMux(in=x, sel=sel[0], a=c, b=d);<br>    DMux(in=y, sel=sel[0], a=e, b=f);<br>    DMux(in=z, sel=sel[0], a=g, b=h);<br>}</pre><p>In this code:</p><ul><li>We use a DMux4Way to split the input in into four intermediate signals, w, x, y, and z, based on the two most significant bits (sel[1..2]) of the selection signal.</li><li>We further split each of these intermediate signals into two output signals based on the least significant bit (sel[0]) of the selection signal:</li><li>We split w into a and b based on sel[0].</li><li>We split x into c and d based on sel[0].</li><li>We split y into e and f based on sel[0].</li><li>We split z into g and h based on sel[0].</li></ul><p>These components are critical in digital circuits, allowing for efficient data routing and distribution. They are easily implemented using HDL for creating and simulating digital systems. If you want to see more examples, go to my <a href="https://github.com/route-2/nand2tetris">GitHub</a>. This is the end of my first week of building a computer from scratch. Stay tuned for the following section, where we’ll look at arithmetic operations on these logic gates.</p><img src="https://medium.com/_/stat?event=post.clientViewed&referrerSource=full_rss&postId=325e1d3e1f2c" width="1" height="1" alt="">]]></content:encoded>
        </item>
    </channel>
</rss>