Paper II — Q8
(a)(i) Prove that the minimum distance of any linear (n, k) block code satisfies dmin ≤ 1 + n – k. (5 marks) (a)(ii) Show that…
Prove that the minimum distance of any linear (n, k) block code satisfies dmin ≤ 1 + n – k. 5 marks
Show that the minimum Hamming distance of a linear block code is equal to the minimum number of columns of its parity check matrix that are linearly dependent. From this conclude that the minimum Hamming distance of a Hamming code is always equal to 3. 15 marks
A commercial interface unit uses different names for the handshake lines associated with the transfer of data from the I/O device into the interface unit. The interface input handshake line is labelled STB (strobe), and the interface output handshake line is labelled IBF (input buffer full). A low-level signal on STB loads data from the I/O bus into the interface data register. A high-level signal on IBF indicates that the data item has been accepted by the interface. IBF goes low after an I/O read signal from the CPU when it reads the content of the data register.
Draw the block diagram showing the CPU, the interface, and the I/O device together with the pertinent interconnections among the three units.
Draw a timing diagram for the handshaking transfer.
Obtain a sequence of events flowchart for the transfer from the device to the interface and from the interface to the CPU. 20 marks
For a 3-bus power system, assume
Voltage at bus – 1 : V₁ = (1·05 + j 0) pu,
Voltage at bus – 2 : V₂ = (0·9812 – j 0·0522) pu and
Voltage at bus – 3 : V₃ = (0·999 – j 0·0468) pu.
The line impedances are shown below :
Bus code Impedances (in p.u.)
1 – 2 (0·02 + j 0·04)
1 – 3 (0·01 + j 0·03)
2 – 3 (0·0125 + j 0·025)
Compute Real and Reactive power loss in all the lines and also compute total system loss. 10 marks
हिंदी में प्रश्न पढ़ें
सिद्ध करें कि किसी रैखिक (n, k) खंड कूट (कोड) की न्यूनतम दूरी का मान dmin ≤ 1 + n – k को संतुष्ट करता है | (5 अंक)
दर्शाइए कि एक रैखिक खंड कूट की न्यूनतम हैमिंग दूरी इसकी पैरिटी चेक मैट्रिक्स जो कि रेखीय आधारित (आश्रित) है के न्यूनतम स्तंभों की संख्या के बराबर है | उपरोक्त से निष्कर्ष निकालिए कि हैमिंग कूट की न्यूनतम हैमिंग दूरी हमेशा 3 होती है | (15 अंक)
एक वाणिज्य अंतःप्रेष्ट इकाई द्वारा I/O युक्ति से अंतःप्रेष्ट इकाई में डाटा स्थानांतरित करने हेतु संबद्ध हैंडशेक लाइनों के लिए भिन्न नामों का उपयोग होता है | अंतःप्रेष्ट निवेशक हैंडशेक लाइन पर STB (स्ट्रोब) अंकित किया गया है व निर्गत हैंडशेक लाइन पर IBF (इनपुट बफर फुल) अंकित किया गया है | निम्नतर संकेत अवस्था में STB डाटा को I/O बस से अंतःप्रेष्ट डाटा पंजी में भारित (लोड) किया जाता है | STB पर उपस्थित उच्च स्तर संकेत दर्शित करता है कि अंतःप्रेष्ट ने डाटा को ग्रहण कर लिया है | CPU से संकेतों को I/O द्वारा पढ़ने के बाद IBF का मान निम्न हो जाता है, जब यह डाटा पंजी के कंटेंट को पढ़ लेता है |
खंड आलेख की सहायता से CPU, अंतःप्रेष्ट व I/O युक्ति को दर्शाते हुए आरेखण करें | साथ ही तीनों इकाइयों के मध्य उपयुक्त अंतरसंयोजनों को भी आलेख में प्रदर्शित करें |
हैंडशेकिंग स्थानांतरण के लिए समय-आलेख का आरेखण करें |
युक्ति से अंतःप्रेष्ट व अंतःप्रेष्ट से CPU में स्थानांतरण की क्रमबद्ध घटनाओं का प्रवाह चार्ट बनायें | (20 अंक)
एक 3-बस शक्ति तंत्र के लिए माने कि
बस न. 1 पर बोल्टता : V₁ = (1·05 + j 0) pu,
बस न. 2 पर बोल्टता : V₂ = (0·9812 – j 0·0522) pu
बस न. 3 पर बोल्टता : V₃ = (0·999 – j 0·0468) pu. है |
लाइनों की प्रतिबाधा निम्नलिखित है :
बस कोड प्रतिबाधा (p.u. में)
1 – 2 (0·02 + j 0·04)
1 – 3 (0·01 + j 0·03)
2 – 3 (0·0125 + j 0·025)
सभी लाइनों में वास्तविक व प्रतिघाती शक्ति की हानि (ह्रास) की गणना करें व तंत्र की संपूर्ण शक्ति हानि की गणना करें | (10 अंक)
The figure this question refers to, in words
The question paper is a scan and the diagram did not survive as text. This is the figure as read from the original page — every component, value and label — so the question can be worked from the text below.
(c) Table: Bus code | Impedances (in p.u.) 1 - 2 | (0.02 + j 0.04) 1 - 3 | (0.01 + j 0.03) 2 - 3 | (0.0125 + j 0.025)
Model answer
Written by UPSC Answer Check against this question's marking rubric, to the expected length. UPSC does not publish answers for Mains — this is one way to score well, not an official key.
(a)(i) Let C be a linear (n,k) code and let H be its parity-check matrix. H has n−k rows, so its n columns h₁,h₂,…,hₙ lie in a vector space of dimension n−k. Hence any n−k+1 columns are linearly dependent. Therefore there exist coefficients cᵢ, not all zero, such that Σ cᵢhᵢ=0 involving at most n−k+1 columns. Then c=(c₁,…,cₙ) is a nonzero codeword because Hcᵀ=0. Its Hamming weight is at most n−k+1. Since dmin is the least nonzero codeword weight, dmin ≤ n−k+1 = 1+n−k.
(a)(ii) Let hᵢ be the columns of H. Any codeword c satisfies Hcᵀ=Σ cᵢhᵢ=0. Thus the nonzero positions of c give a linearly dependent set of columns. If s is the least number of dependent columns, then s ≤ dmin. Conversely, let s be the least number of dependent columns. Since s is minimal, the dependency relation involves all s columns with nonzero coefficients. Define cᵢⱼ=αⱼ on those columns and zero elsewhere. Then c is a nonzero codeword of weight s, so dmin ≤ s. Hence dmin=s.
For a binary Hamming code of order m≥2, H has all nonzero m-tuples as columns. No one or two columns are dependent: no zero column, and two binary nonzero columns are dependent only if equal. For any two distinct columns a,b, a+b is nonzero and distinct from a,b, hence is another column c. Thus a+b+c=0, so three columns are dependent. Therefore the least dependent column set has size 3, and dmin=3.
(b)(i) Block diagram: `` +------+ data/address/control +-------------+ I/O data bus +------------+ | CPU |<---------------------->| Interface |<-------------->| I/O device | | | RD ------------------>| data register| STB(low) ---->| | +------+ | | IBF(high) --->| | +-------------+ +------------+ `` STB is from device to interface, active low. IBF is from interface to device, active high. CPU uses data, address and read control lines.
(b)(ii) Timing diagram: `` I/O data: ----< D valid >------------------- STB: ‾‾‾‾‾________________/‾‾‾‾‾‾‾‾‾‾ IBF: ________/‾‾‾‾‾‾‾‾‾‾‾‾‾‾‾‾______ CPU RD: ‾‾‾‾‾‾‾‾‾‾‾‾‾‾‾‾‾‾‾‾______/‾‾‾‾ CPU data: ----------------------< D >------- `` The device puts data on the I/O bus and makes STB low. The interface loads the data and makes IBF high. When CPU reads, RD goes low; the interface drives data to CPU and then clears IBF low.
(b)(iii) Sequence of events flowchart: Device side: wait until IBF=0 → place data on I/O bus → make STB=0 → wait for IBF=1 → remove data; make STB=1 → wait for IBF=0 for next item.
Interface side: on STB=0, load data into register → set IBF=1 → on CPU RD=0, place register data on CPU data bus → clear register → set IBF=0.
CPU side: test ready flag or receive interrupt → issue RD=0 → read data → issue RD=1 → repeat.
(c) Use Iᵢⱼ=(Vᵢ−Vⱼ)/Zᵢⱼ and S_lossᵢⱼ=|Iᵢⱼ|²Zᵢⱼ=Pᵢⱼ+jQᵢⱼ. Shunt loss is neglected.
Line 1–2: V₁−V₂=0.0688+j0.0522; |ΔV|²=0.00745828; |Z₁₂|²=0.0020. |I₁₂|²=3.72914. P₁₂=3.72914×0.02=0.0745828 pu; Q₁₂=3.72914×0.04=0.1491656 pu.
Line 1–3: V₁−V₃=0.051+j0.0468; |ΔV|²=0.00479124; |Z₁₃|²=0.0010. |I₁₃|²=4.79124. P₁₃=4.79124×0.01=0.0479124 pu; Q₁₃=4.79124×0.03=0.1437372 pu.
Line 2–3: V₂−V₃=−0.0178−j0.0054; |ΔV|²=0.00034600; |Z₂₃|²=0.00078125. |I₂₃|²=0.44288. P₂₃=0.44288×0.0125=0.005536 pu; Q₂₃=0.44288×0.025=0.011072 pu.
Total real loss: P_loss=0.0745828+0.0479124+0.005536=0.1280312 pu.
Total reactive loss: Q_loss=0.1491656+0.1437372+0.011072=0.3039748 pu.
Total system loss = 0.1280312 + j0.3039748 pu.
What "Prove" is asking you to do
Establish that the statement holds for every case it claims, not for one representative case. The argument must be closed: each line follows from a definition, a hypothesis, or a named theorem you are entitled to use.
Structure that answers it
Given and to prove, restated → theorem or construction to be used, named → the argument line by line → conclusion stated as proved
Where marks are lost
Testing one example, which illustrates but proves nothing. On an if and only if claim, proving one direction and stopping forfeits that half outright, and degenerate cases — zero, the empty set, the equality case — have to be disposed of rather than assumed away.
How this answer will be evaluated
Approach
(a(i)) derive: given > assumptions > stepwise derivation > result > check | (a(ii)) derive: given > assumptions > stepwise derivation > result > check | (b) describe: define > structure or process in order > labelled diagram > significance | (c) calculate: given > formula > substitution > result with units > interpretation Full marks: All parts fully answered with correct derivations, diagrams, and calculations; clear and precise.
Key points expected
- Define minimum distance d_min
- Relate code dimension k to redundancy n-k
- Establish inequality d_min ≤ 1 + n - k
- Logical step-by-step derivation
- Show d_min equals min dependent columns of H
- Define Hamming code parity check matrix H
- Prove no two columns are linearly dependent
- Conclude d_min = 3 for Hamming codes
Evaluation rubric
Each sub-part is marked on its own, against the marks and word limit printed on the paper.
- (a(i)) Proof of the Singleton bound for linear block codes. 5 marks
derive— given → assumptions → stepwise derivation → result → check
Must cover
- Define minimum distance d_min
- Relate code dimension k to redundancy n-k
- Establish inequality d_min ≤ 1 + n - k
- Logical step-by-step derivation
Loses marks
- Stating result without proof
- Confusing d_min with code rate
Earns more
- Mention Singleton bound by name
- Reference to MDS codes
Extra mark
- Example of a code meeting the bound
- (a(ii)) Link d_min to parity check matrix columns and apply to Hamming codes. 15 marks
derive— given → assumptions → stepwise derivation → result → check
Must cover
- Show d_min equals min dependent columns of H
- Define Hamming code parity check matrix H
- Prove no two columns are linearly dependent
- Conclude d_min = 3 for Hamming codes
Loses marks
- Skipping the linear dependence proof
- Incorrect definition of Hamming code H matrix
Earns more
- Explicit column vector examples
- Connection to error correction capability
Extra mark
- Generalization to other linear codes
- (b) Block diagram, timing diagram, and flowchart for I/O handshaking. 20 marks
describe— define → structure or process in order → labelled diagram → significance
Must cover
- Block diagram with CPU, interface, I/O device
- Label STB and IBF handshake lines correctly
- Timing diagram showing STB low and IBF high/low transitions
- Flowchart for device-to-interface and interface-to-CPU transfer
Loses marks
- Missing or mislabeled handshake lines
- Timing diagram without clear signal transitions
Earns more
- Clear signal polarity annotations
- Synchronized timing edges
Extra mark
- Note on interrupt or polling mechanism
- (c) Compute real and reactive power loss in each line and total system loss. 10 marks
calculate— given → formula → substitution → result with units → interpretation
Must cover
- Calculate current in each line using V and Z
- Compute P_loss and Q_loss per line
- Sum for total system loss
- Use per-unit system consistently
Loses marks
- Arithmetic errors in complex power calculation
- Omitting reactive power loss
Earns more
- Show intermediate current calculations
- State assumptions (e.g., balanced system)
Extra mark
- Comment on loss distribution or efficiency
Practice this exact question
Write your answer and it is marked point by point against the model answer above — what you covered, what you missed, what you got wrong.
Evaluate my answer →More from Electrical Engineering 2021 Paper II
- Q5 (a) Explain the ratio error and phase angle error of current transformer. 10 marks (b) Th…
- Q6 (a) A synchronous machine is connected to an infinite bus through a transformer and a dou…
- Q7 (a) Discuss the percentage differential Relay with harmonic restraint with the help of di…
- Q8 (a)(i) Prove that the minimum distance of any linear (n, k) block code satisfies dmin ≤ 1…