COMPUTER NETWORKING-ERROR DETECTION.pptx

Computer Networking

1. NETWORKING Error Detection and Error Correction - Fundamentals, Block coding, CRC, Hamming Code. Network Layer: Internetworking Devices. IP Addressing and Subnetting, Network Layer Protocols: IPV4, IPV6 and ICMP. Address Mapping: ARP, RARP and DHCP. Routing algorithms (link state and distance vector).

2. Error Detection and Error Correction

3.   Error Detection and Error Correction  Error Detection Purpose: To recognize if data has been altered during transmission due to noise, interference, or faults. How It Works: Sender adds extra (redundant) bits to the original data using specific algorithms. Common Techniques: Parity Bits: Add a single bit to ensure the number of 1s is even (even parity) or odd (odd parity). Checksums: Data is added or processed into a summary value; the receiver recomputes and compares. Cyclic Redundancy Check (CRC): Uses polynomial division to generate a unique code for blocks of data. Detection Only: Most methods only detect errors; they cannot correct them.

4. Error Correction Purpose: Not only detects, but also corrects errors without retransmission. How It Works: Adds more redundancy for receivers to pinpoint and fix errors. Common Techniques: Forward Error Correction (FEC): Redundant data bits are used by the receiver to reconstruct original data. Hamming Code: Locates and corrects single-bit errors, detects double-bit. Reed-Solomon Codes: Effective for burst errors (multiple bits at once); used in CDs, DVDs. Trade-offs: Higher error correction capability requires more bandwidth and complexity.

5. Examples-Error Detection

6. Examples-Error Correction  

7. Block Coding What is Block Coding? Principle: Data is divided into fixed-size segments or "blocks" (e.g., 4 bits). Encoding: Each block (k data bits) is transformed into a longer block (n bits) by adding r = n-k redundant bits. Example: For a (7,4) block code, 4 data bits are encoded into 7 bits with 3 redundant bits. Key Points: Systematic Codes: The original data bits appear unchanged in the encoded output, followed by redundant bits. Redundant Bits: Calculated based on the original data using a pre-defined logic or matrix. Error Detection/Correction: Block codes can be designed to detect/correct certain numbers of errors per block. Hamming Distance: The minimum number of differing bits between any two codewords; higher distance allows better error detection/correction. Examples of Block Codes: Parity Code: Adds one bit for parity. Hamming Codes: (7,4), (15,11), etc.—correct single errors. Reed-Solomon Codes: Correct burst errors; used in CDs, DVDs, QR codes.

8. Cyclic redundancy check  (CRC) A  cyclic redundancy check  (CRC) is an error-detecting code commonly used in digital networks and storage devices to detect accidental changes to digital data. It is an error-detecting code used to  determine if a block of data has been corrupted . CRCs are ubiquitous. CRC uses Generator Polynomial which is available on both sender and receiver side. An example generator polynomial is of the form like x 3  + x + 1. This generator polynomial represents key 1011. They are present in many of the link layers that TCP/IP is used over. For instance, Ethernet and Wi-Fi packets both contain CRCs. The mathematics behind CRCs initially appears daunting, but it doesn’t have to be. The idea is given a block of N bits, let’s compute a checksum of a sort to see if the N bits were damaged in some way, for instance by transit over a network

9. How does CRC Work? Error correction goes way back in computing. One of the first things I ran into while understanding the ASCII character set was  parity . The seven-bit ASCII character set in some computers used the 8th bit as a check bit to see if the character had been transmitted correctly. If the character had an odd number of ones in the lower 7 bits, the 8th bit was set to a 1, otherwise 0. So if the receiving device (modem, computer terminal, etc.) got an 8-bit quantity where the number of ones in it was not even, it knew that character had been corrupted. This is a simplistic scheme, but some important concepts shared with the CRC are here: We added the check data to the transmitted data (a redundancy), and It isn’t perfect — it only detects certain errors that it was designed to check.  (Specifically, the parity bit successfully detects all one-bit errors in each 7-bit block of data, but potentially can fail if worse data corruption occurs.)

10. Examples For example, let’s say we want to add 0101b + 1110b. With carries we see: 11 0101b +1110b ------ 10011b Let’s just do the binary math without carries and see the difference: 0101b +1110b ------ 1011b

11. Examples

12. Examples

13. Hamming Code Hamming code is a set of error-correction codes that can be used to  detect and correct the errors that can occur when the data is moved or stored from the sender to the receiver. It is  technique developed by R.W. Hamming for error correction . In this coding method, the source encodes the message by inserting redundant bits within the message. These redundant bits are extra bits that are generated and inserted at specific positions in the message itself to enable error detection and correction. When the destination receives this message, it performs recalculations to detect errors and find the bit position that has error. Due to the limited redundancy that Hamming codes add to the data, they can only detect and correct errors when the error rate is low. This is the case in computer memory (usually RAM), where bit errors are extremely rare and Hamming codes are widely used, and a RAM with this correction system is a ECC RAM ( ECC memory ). In this context, an extended Hamming code having one extra parity bit is often used. Extended Hamming codes achieve a Hamming distance of four, which allows the decoder to distinguish between when at most one one-bit error occurs and when any two-bit errors occur.

14. Hamming code Encoding a message by Hamming Code The procedure used by the sender to encode the message encompasses the following steps − Step 1  − Calculation of the number of redundant bits. Step 2  − Positioning the redundant bits. Step 3  − Calculating the values of each redundant bit.

15. Hamming Code Decoding a message in Hamming Code Once the receiver gets an incoming message, it performs recalculations to detect errors and correct them. The steps for recalculation are − Step 1  − Calculation of the number of redundant bits. Step 2  − Positioning the redundant bits. Step 3  − Parity checking. Step 4  − Error detection and correction

16. Examples-1

17. Examples-2

18. NETWORK LAYER

19. What are Internetworking Devices? Internetworking devices operate at the Network Layer (Layer 3) of the OSI model to connect multiple networks, manage traffic, and direct data packets between networks of different sizes, types, or protocols. 1. Router Definition: A device that receives, analyzes, and forwards data packets between computer networks based on IP addresses. Functions: Determines the best path for data to travel to its destination. Connects LANs and WANs, forming the backbone of the internet. Supports NAT (Network Address Translation) for sharing public IPs. Performs packet filtering for security (access control lists). Key Feature: Maintains routing tables and uses protocols like RIP, OSPF, BGP. Example: Home internet routers, enterprise core routers. 2. Layer-3 Switch Definition: A high-performance device combining the speed of switching (hardware-based forwarding) with the intelligence of routing (using IP addresses). Functions: Forwards packets between VLANs or subnets within large LANs. Implements basic routing features alongside switching. Usage: Frequently used in large corporate LANs to reduce latency and simplify network design.

20. 3. Gateway Definition: Network device (hardware/software) that connects two networks using different protocols. Functions: Translates data formats, protocols, or addresses (protocol conversion). Enables communication between systems using different architectures (e.g., TCP/IP to AppleTalk). Examples: VoIP gateways, email gateways, cloud application gateways. 4. Other Devices (Mention for completeness) Modem: Converts digital signals to analog for transmission over telephone lines, and vice versa (operates primarily at Layers 1 & 2 but involved in internetworking). Firewall: Filters incoming and outgoing traffic, can be combined with routers (Layer 3/4). Device OSI Layer(s) Main Function Example Use Case Router Layer 3 Routes packets between networks Internet gateways, WAN links L3 Switch Layer 2 & 3 High-speed routing within LANs Large campus or enterprise LANs Gateway All/varies Protocol conversion and translation Connecting TCP/IP to legacy WAN Modem Layers 1 & 2 Analog/digital conversion Home internet over phone lines

21. What is an IP Address? An IP (Internet Protocol) address is a unique identifier assigned to each device on a network to enable routing of data between devices. IPv4 Addressing Length: 32 bits (4 bytes) Format: Written as four decimal numbers (octets), each ranging from 0 to 255, separated by dots. Example: 192.168.1.1 Address space: Around 4.3 billion unique addresses (2³²) Structure: Divided into Network and Host parts based on subnet mask/class. Usage: Most commonly used in traditional networks. IPv6 Addressing Length: 128 bits (16 bytes) Format: Written as eight groups of 4 hexadecimal digits, separated by colons. Example: 2001:0db8:85a3:0000:0000:8a2e:0370:7334 Address space: Enormous, approximately 3.4 × 10³⁸ addresses (2¹²⁸), enough for virtually unlimited devices. Advantages: Auto-configuration, built-in security (IPSec), better routing efficiency.

22. Comparison of IPv4 and IPv6 Feature IPv4 IPv6 Address Bits 32 bits 128 bits Address Format Dotted-decimal, e.g., 192.168.1.1 Hexadecimal colon-separated, e.g., 2001:0db8::8a2e:0370:7334 Address Space About 4.3 billion addresses About 3.4 × 10³⁸ addresses Example 192.168.1.1 2001:0db8:85a3:0000:0000:8a2e:0370:7334

23. What is Subnetting? Subnetting is the process of dividing a large network (IP address block) into smaller, more manageable segments called subnets. Key Concepts and Details Purpose: Facilitates efficient use of IP addresses. Segregates network traffic, reducing congestion and enhancing security. Helps contain broadcast traffic within each subnet. Subnet Mask & CIDR: Subnet Mask: Specifies which part of an IP address is the network portion and which part is for hosts. Example: 255.255.255.0 (corresponds to /24) CIDR Notation: Expresses subnet masks as a suffix to the IP address, showing the number of bits as network address. Example: 192.168.10.0/24 Subnet Calculation: Number of possible subnets = 2^n, where n = number of bits borrowed for subnetting. Number of usable hosts per subnet = 2^h - 2, where h = number of host bits. Example: Original Block: 192.168.1.0/24 (256 addresses) If split into 4 subnets (/26): each subnet gets 64 addresses; 62 usable hosts per subnet.

24. Subnetting(CONT.) Benefits: Enhanced network security by isolating broadcast domains. Improves network performance and simplifies management. Streamlines IP address allocation and reduces wasted space. Visual Suggestions: Diagram showing large network divided into subnets. Example of binary-to-decimal conversion for subnet masking.

25. Network Layer Protocols Major Protocols at the Network Layer IPv4 Widely used, but address exhaustion is leading to IPv6 adoption. Allows fragmentation for large packets. Uses address classes (A, B, C, D, E) and supports subnetting. Example address: 192.0.2.1 IPv6 Very large address space (3.4 × 10³⁸ addresses). No need for NAT; each device can get a unique global address. Built-in security with mandatory support for IPSec. Facilitates auto-configuration via Stateless Address Autoconfiguration (SLAAC). ICMP (Internet Control Message Protocol) Not used for transporting user data. Used by networking devices to send error messages (e.g., "host unreachable") and perform diagnostics (e.g., ping). Integral to both IPv4 (ICMPv4) and IPv6 (ICMPv6). Protocol Version Address Size Major Features IPv4 4 32 bits Connectionless, fragmentation, header checksums IPv6 6 128 bits Large address space, auto-configuration, security (IPSec), simplified headers ICMP - N/A (auxiliary) Error reporting, diagnostic messages (e.g., ping, traceroute)

26. Address Mapping Protocols ARP (Address Resolution Protocol) Purpose: Resolves an IPv4 address (logical address) to a corresponding MAC address (physical hardware address) within a local area network (LAN). How it Works: When a device wants to communicate within a LAN, it checks its ARP cache for the destination's MAC. If not found, it broadcasts an ARP request: “Who has IP x.x.x.x ?” The device with that IP replies with its MAC address, which is then cached for future use. Characteristics: Operates at the boundary of Layer 2 (Data Link) and Layer 3 (Network) of the OSI model. Essential for Ethernet communication. Vulnerable to spoofing attacks if not secured. RARP (Reverse Address Resolution Protocol) Purpose: Allows a device to request its own IP address from a network, given only its MAC address. Use case: Primarily used by diskless workstations or devices without permanent storage. Operation: The device broadcasts a RARP request; a RARP server replies with the device’s IP address. Current Status: Obsolete—largely replaced by more versatile protocols like BOOTP and DHCP.

27. Address Mapping Protocols(CONT.) DHCP (Dynamic Host Configuration Protocol) Purpose: Automatically assigns IP addresses and other network configuration parameters (subnet mask, gateway, DNS servers) to devices on a network. How it Works: Device broadcasts a DHCPDISCOVER when joining a network. DHCP server responds with an IP lease (DHCPOFFER), and device requests it (DHCPREQUEST). Server confirms (DHCPACK), after which device uses assigned IP settings. Features: Supports static and dynamic address assignment, automatic IP reuse, and address leasing (addresses are temporary). Manages large networks efficiently, reduces manual errors, and allows seamless device mobility.

28. Routing Algorithms Link State Algorithm (e.g., OSPF) Overview: Each router has complete knowledge of the entire network topology. This means every router knows all routers and the state (status and cost) of all links in the network. Information Sharing: Routers do not share full routing tables with neighbors. Instead, they exchange Link State Advertisements (LSAs) that describe the state of their directly connected links only. How It Works: When a router detects a change (new connection, broken link), it generates an LSA describing its local link state. This LSA is flooded to all other routers in the network so that each router ends up with identical link state databases. Using this global topology, each router computes the shortest path to every destination using Dijkstra's algorithm. Advantages: Faster convergence after topology changes because routers know the full map. Avoids persistent routing loops. More scalable for large, complex networks. Provides more accurate routing decisions due to global knowledge. Disadvantages: Higher CPU and memory usage on routers due to handling of link state databases. More bandwidth used initially due to flooding LSAs. Example Protocol: OSPF (Open Shortest Path First) is a widely used link state routing protocol.

29. Distance Vector Routing Overview: Each router shares only its routing table or vector containing the shortest distances (costs) to known destinations with its immediate neighbors. Information Sharing: Routers periodically send their entire routing tables to neighbors, not just changes. Updates happen at regular intervals regardless of changes. How It Works: Routers get routing info from neighbors. They update their tables by adding the cost to each neighbor plus the neighbor’s advertised costs to destinations. The best (minimum cost) paths are selected. This iterative process continues until routing tables converge. Advantages: Simple to configure and implement. Uses less memory and CPU resources on routers. Requires less bandwidth for updates per exchange compared to full flooding. Disadvantages: Slow convergence, especially after failures. Susceptible to the count-to-infinity problem (routing loops). Less scalable for large networks. Technique to Alleviate Problems: Mechanisms like split horizon, route poisoning, and hold-down timers are used to reduce routing loops and speed convergence. Example Protocol: RIP (Routing Information Protocol) is a classic distance vector routing protocol using hop count as cost. Routing Algorithms (CONTI.)

30. Routing Algorithms (CONTI.) Feature Link State (e.g., OSPF) Distance Vector ( e.g ., RIP) Routing Information Shares link states of directly connected links (LSAs) Shares entire routing table periodically with neighbors Network Knowledge Global view of entire network topology Only aware of neighbors' routing tables Routing Algorithm Dijkstra's shortest path algorithm Bellman-Ford algorithm Convergence Speed Fast Slow Bandwidth Usage Higher (due to flooding LSAs initially) Lower (periodic updates, smaller messages) CPU and Memory Usage High (stores complete topology and computes paths) Low Loop Avoidance No persistent loops, transient only Susceptible to persistent loops (count-to-infinity) Scalability Scales well to large and complex networks Suited for smaller networks Update Triggers Event-driven (only on topology changes) Periodic (at fixed intervals) Comparison Table

31. Q & A Q1) Explain in detail the principles and methods of error detection and error correction used in digital communication systems. Illustrate with suitable examples. Ans) Error detection and correction are essential for ensuring the accuracy and reliability of digital communication. They are used to identify and fix errors introduced during transmission due to noise, interference, or hardware faults. Error Detection Methods: Parity Bit: Adds a single parity bit to data to ensure the number of 1s is even (even parity) or odd (odd parity). Detects single-bit errors but cannot locate or correct errors. Example: For data "1011", even parity bit = 1 (total 1s = 4). Checksum: Data is divided into equal-sized segments; all segments are summed using one's complement arithmetic. The receiver checks the sum of received data and the checksum. Common in TCP/IP networks. CRC (Cyclic Redundancy Check): Treats data as a binary polynomial and divides it by a fixed generator polynomial. Remainder of this division (CRC bits) is appended to the data. Receiver performs the same division and checks if the remainder is zero. Effective for detecting burst errors.

32. Error Correction Methods: Hamming Code: Adds multiple parity bits to data to allow detection and correction of single-bit errors. Example: Hamming (7,4) code encodes 4 bits into 7 by adding 3 parity bits. Can detect and correct single-bit errors. Reed-Solomon Code: Block-based code suitable for correcting burst errors. Used in CDs, DVDs, QR codes. Example: Original data: "1011". Encoded using Hamming (7,4): "1011010". If one bit flips (e.g., "1011110"), receiver uses parity to locate and correct it.

33. Q2. Discuss block coding in detail. How does block coding enhance data reliability? Explain with an example of Hamming(7,4) code. Ans) Block coding divides data into fixed-size blocks of k bits, which are then transformed into n-bit codewords by adding r (n-k) redundant bits. This redundancy enables error detection and, in many cases, error correction. Process: Divide the message into k-bit blocks (data words). Use an encoding scheme to generate r redundant bits based on each k-bit block. Combine the k data bits and r redundancy bits to form an n-bit codeword. Transmit the codeword. The receiver decodes and checks for errors using the redundant bits. Hamming (7,4) Code Example: k = 4 data bits, r = 3 parity bits, n = 7. Data: D1 D2 D3 D4 Codeword: P1 P2 D1 P3 D2 D3 D4, where P1, P2, and P3 are parity bits computed from specific subsets of data bits. Suppose the data is "1101": Arrange: _ _ 1 _ 1 0 1 Compute P1 (parity for bits 1,3,5,7), P2 (2,3,6,7), P3 (4,5,6,7) based on even parity. After calculation, suppose the final codeword sent is "1011011". If a single-bit error occurs during transmission, the receiver calculates the syndrome using parity check equations. The result locates and corrects the error, restoring the original 4-bit data.

34. Q3. Explain with diagrams the process of IP addressing, subnetting, and address mapping (ARP, RARP, DHCP) in the context of the network layer. Ans) IP Addressing: Each device in a network receives a unique IP address (IPv4: 32 bits, e.g., 192.168.1.15). The address has a network portion (identifies the network) and a host portion (identifies the device within the network). Subnetting:  Divides a single large network into smaller, manageable sub-networks (subnets) by applying a subnet mask. For instance, 192.168.1.0/24 can be divided into four /26 subnets, each with 62 usable hosts. Example Diagram Description:   Imagine a network 192.168.1.0/24 divided into subnets: 192.168.1.0/26 (hosts: 1-62) 192.168.1.64/26 (hosts: 65-126) ...and so on. Address Mapping Protocols: ARP (Address Resolution Protocol): Resolves an IP address to a MAC (hardware) address on a local network. When device A wants to communicate with device B, it uses ARP to find B's MAC address, then sends frames at the Data Link Layer. RARP (Reverse ARP): Maps a known MAC address to an IP address, helping devices such as diskless workstations obtain their IP address at boot. DHCP (Dynamic Host Configuration Protocol): Automatically assigns IP addresses and other network configurations to devices. When a device joins the network, it sends a DHCPDISCOVER broadcast, and a DHCP server offers an IP address. The device requests and then receives confirmation, minimizing human configuration. Each protocol streamlines network operations: ARP  ensures devices know each other's hardware addresses for packet delivery within a LAN. RARP  allows devices to learn their IPs when they cannot be set statically. DHCP  provides dynamic address management for scalability. In practice: When a PC connects to a network, it may use DHCP to obtain an IP address. To send data, it uses ARP to map the destination IP to a MAC address, then frames data accordingly for transmission.

35. Q4. Compare and contrast the distance vector and link state routing algorithms. Discuss their working, advantages, disadvantages, and examples . Ans) Distance Vector Routing: Each router maintains a table (vector) of minimum distances to every other router and the next hop to reach them. Routers periodically exchange their vectors with direct neighbors. Update is based on Bellman-Ford algorithm. Working: Routers send their distance vector tables to neighbors at regular intervals. Each router updates its table based on neighbors’ information, adding the cost to reach the neighbor. Over time, tables converge to show shortest paths. Pros: Simple to implement. Suitable for small networks. Cons: Slow convergence, especially after a topology change (e.g., route failure). Prone to routing loops and "count to infinity" problems. Example:  RIP (Routing Information Protocol). Link State Routing: Each router constructs a map (topology) of the entire network by exchanging link state advertisements (LSAs). Uses Dijkstra's algorithm to compute the shortest path to all destinations.

36. Working: When a change occurs, routers flood the network with LSAs describing their directly connected links. All routers build the same topology database. Routers independently compute routing tables using the database. Pros: Faster convergence. Scales better to large and complex networks. Robust against routing loops. Cons: More complex and resource-intensive. Requires more memory and CPU. Example:  OSPF (Open Shortest Path First), IS-IS. In summary: Distance vector: easy, but less scalable and slower to react. Link state: scalable and converges quickly, but more complex to manage.

37. Q5. Describe in detail the working of the Cyclic Redundancy Check (CRC) algorithm. Why is CRC preferred over simple parity and checksum methods? Ans) CRC (Cyclic Redundancy Check) is a powerful error-detection method used in digital networks and storage devices. How CRC Works: The data block (treated as a binary number) is divided by a predetermined "generator" polynomial. The remainder of this division (CRC bits) is appended to the data and transmitted. The receiver performs the same division on the received data + CRC. If the result is zero, the data is considered error-free; otherwise, an error is detected. Example: Data: 101101, Generator polynomial: 1101 (degree-3). 3 zeros are appended: 101101000. Perform binary division (modulo-2 division) by 1101; remainder is CRC. Transmit data + CRC. Receiver checks by dividing received bits by generator polynomial.

38. Why CRC is Preferred: Can detect all single-bit and double-bit errors, as well as burst errors up to the length of the CRC. Much stronger at detecting common error patterns compared to parity bits and checksums, which may miss some errors. Used in Ethernet, USB, and many storage devices for its robustness. Comparisons: Parity Bit: Can detect only odd numbers of errors (often only single-bit). Checksum: Better than parity but less robust than CRC, can miss some burst errors.

39. Q6. A company has been allocated the network 192.168.10.0/24. It needs 4 subnets of equal size. (a) What will be the subnet mask? (b) What is the range of IP addresses for each subnet? Ans) (a) We need 4 subnets → 2 bits for subnetting (2²=4), so mask: /26 = 255.255.255.192 (b) Each subnet has 64 addresses (256/4). Subnet ranges: Subnet 1: 192.168.10.0 – 192.168.10.63 Subnet 2: 192.168.10.64 – 192.168.10.127 Subnet 3: 192.168.10.128 – 192.168.10.191 Subnet 4: 192.168.10.192 – 192.168.10.255

40. Q7. How many parity bits are required to create a Hamming code for 11 data bits? Show your calculation. Ans) Formula: 2^r ≥ k + r + 1 Let k=11, find minimum r: Try r=4: 2⁴=16 < 11+4+1=16 (just equal) Try r=5: 2⁵=32 ≥ 11+5+1=17 → satisfies. So, 5 parity bits needed for 11 data bits. Q8. A router knows the following distances to its neighbors: A (2), B (7), C (3). If its neighbors report their own minimum distances to a destination D as: A: 4 B: 2 C: 6 What is the router's minimum distance to D using the distance vector algorithm? Answer: Calculate cost via each neighbor: Via A: 2 (to A) + 4 (A to D) = 6 Via B: 7 + 2 = 9 Via C: 3 + 6 = 9 Minimum is 6 via A.

41. Q9. What is the maximum number of usable hosts in a subnet with subnet mask 255.255.255.224? Answer: This is a /27, so: 32 IPs (2^(32-27)=32), usable: 32-2=30. Q10. Given codewords 1010101, 1110101, 1000101, 1000001, what is the minimum Hamming distance of this code? Answer: Find minimum bit difference between any two codewords: 1010101 vs 1110101: diff in 2nd bit → distance = 1 1010101 vs 1000101: diff in 3rd bit → distance = 1 1000101 vs 1000001: diff in 5th bit → distance = 1 Minimum distance is 1.

42. Q11. Two 8-bit words to send: 11010101 and 10111001. What is the 8-bit checksum sent? Answer: Sum: 11010101 [phone] =11010101 + 10111001 = 11010101 [phone] 11010101 [phone] = 11010101 + 10111001 = 11010101 Carry out binary addition: 11010101 [phone] 11010101 [phone] = 11010101 [phone] = 1 1 0 1 0 1 0 1 (binary 213) [phone] (binary 185) =1 1 0 1 0 1 0 1 [phone] =1 1 0 1 0 1 0 1 [phone] Sum: 11010101 + 10111001 = 11010101 [phone] Let's do it step by step: 11010101 (213) 10111001 (185) = 398, which is 110001110 in binary (9 bits). Wraparound: add leftmost (carry) bit to rightmost 8 bits: 10001110 + 1 = 10001111 Take 1’s complement: 1's complement of 10001111 is 01110000 So, checksum sent is 01110000.

43. Q12. For a 7-bit Hamming (7,4) code, a received codeword is 1100111. What is the original 4-bit data, and was there an error? Show your calculation. Answer: Positions: 1(P1), 2(P2), 3(D1), 4(P3), 5(D2), 6(D3), 7(D4) Received: 1 1 0 0 1 1 1 Calculate syndrome bits (even parity): S1 = positions 1,3,5,7 → 1,0,1,1 → 1+0+1+1=3 (odd) → S1=1 S2 = positions 2,3,6,7 → 1,0,1,1=1+0+1+1=3 (odd) → S2=1 S3 = positions 4,5,6,7 → 0,1,1,1=0+1+1+1=3 (odd) → S3=1 Syndrome: S3 S2 S1 = 1 1 1 = 7 (binary) So, error in position 7. Correct bit 7 (from 1 to 0): new codeword = 1100110 Original data bits: D1,D2,D3,D4 = positions 3,5,6,7 = 0 1 1 0 Final answer: Data bits sent: 0 1 1 0 Single-bit error detected and corrected at bit 7.

44. Q13. Given data bits 110101 and generator 1011, find the CRC code sent (Show the division). Answer: Append 3 zeros (since generator is 4 bits): 110101000 Divide by 1011 using binary division: 1101 ÷ 1011 → 0110 (remainder: after 1st step) Take next bit down, repeat XOR process... Working out: Step 1: 1101 XOR 1011 = 0110 (bring down next digit, making 1100) Step 2: 1100 XOR 1011 = 0111 (bring down next digit, making 1110) Step 3: 1110 XOR 1011 = 0101 (bring down next digit, making 0101) Step 4: 1010 XOR 1011 = 0001 (since only 3 digits left, remainder is 100) So CRC is 100. Transmitted frame: Data + CRC = 110101100

45. Q14. A company has been allocated the network 192.168.10.0/24. It needs 4 subnets of equal size. (a) What will be the subnet mask? (b) What is the range of IP addresses for each subnet? Answer: (a) We need 4 subnets → 2 bits for subnetting (2²=4), so mask: /26 = 255.255.255.192 (b) Each subnet has 64 addresses (256/4). Subnet ranges: Subnet 1: 192.168.10.0 – 192.168.10.63 Subnet 2: 192.168.10.64 – 192.168.10.127 Subnet 3: 192.168.10.128 – 192.168.10.191 Subnet 4: 192.168.10.192 – 192.168.10.255

46. Q15. Given dataword  1001 and divisor 1011 (CRC-3), find the CRC bits. Solution: Dataword : 1001, Generator: 1011 (degree 3, so append 3 zeros): 1001 000 Divide 1001000 by 1011 (binary long division). The CRC is 100. Transmitted codeword: 1001 100. Q16. For the message 11000 and generator polynomial x3+x+1x3+x+1 (binary: 1011), what is the CRC value? Solution: Message: 11000, Append 3 zeros: 11000 000 Divide by 1011: The remainder (CRC) is 100. Transmitted code: 11000 100. Q17. A bitstream 1101011011 is to be transmitted using CRC with the generator polynomial x4+x+1x4+x+1 (binary: 10011). Find the transmitted codeword. Solution: Append 4 zeros: 1101011011 0000. Perform binary division (modulo-2) by 10011. The remainder is 1110. Transmitted codeword: 1101011011 1110.

47. Q18. A 7-bit Hamming codeword received is 1011011. Detect and correct the error, then give the original 4-bit data. Solution: Positions: 1(P1) 2(P2) 3(D1) 4(P3) 5(D2) 6(D3) 7(D4) Received: 1 0 1 1 0 1 1 Calculate the syndrome: S1 (positions 1,3,5,7): 1+1+0+1=3 (odd) → S1=1 S2 (2,3,6,7): 0+1+1+1=3 (odd) → S2=1 S3 (4,5,6,7): 1+0+1+1=3 (odd) → S3=1 Syndrome: 111 = 7 (error at position 7) Flip last bit: new codeword 1011010 Original data: D1 D2 D3 D4 = 1 0 1 0 Answer: Error at position 7 (corrected). Original data: 1 0 1 0 Q19. How many parity bits are required for 8 data bits in Hamming code? Write the formula. Solution: Formula: 2r≥k+r+12r≥k+r+1, where k=8k=8. Try r=4→24=16≥8+4+1=13r=4→24=16≥8+4+1=13 (satisfies). Answer: 4 parity bits.

48. Q20. Compute the 16-bit checksum for two data segments: 1001001110010011 and 1001100001001101. Solution: Add: 1001001110010011 + 1001100001001101 = 10010101111100000 (17 bits) Wrap extra bit: 0010101111100000 + 1 = 0010101111100001 Take 1's complement: 1101010000011110 Answer:  Checksum = 1101010000011110. Q21.Given four 8-bit words sent: 10011001, 11100010, 00100100, 10000100, compute the sent checksum. Solution: Add all four: 10011001 + 11100010 = 101111011 101111011 + 00100100 = 110000111 110000111 + 10000100 = 100100011 Wrap and sum if over 8 bits, then complement all bits. Final checksum is 01101100.