گیت XOR و مقایسه‌گر برابری

فرض کن لامپ راه‌پله را با دو کلید کنترل می‌کنی: یکی پایین پله‌ها و یکی بالای آن. هر کلید باید بتواند به‌تنهایی وضعیت لامپ را عوض کند، بی‌آنکه بداند کلید دیگر در چه حالتی است. هیچ‌کدام از AND و OR این رفتار را نمی‌سازند؛ آنچه لازم داری گیت XOR است، گیتی که به «تفاوت» حساس است نه به «بودن یا نبودن».

تعریف XOR و XNOR

گیت XOR که به آن «یای انحصاری» می‌گویند، خروجی ۱ می‌دهد اگر و فقط اگر دو ورودی‌اش با هم متفاوت باشند؛ اگر هر دو ۰ یا هر دو ۱ باشند خروجی ۰ است. همین گیت را می‌توان با AND و OR و NOT بازنویسی کرد: خروجی برابر است با «A و نهِ B» یا «نهِ A و B». نمادش را با علامت جمع درون دایره می‌نویسند. وارونهٔ آن، یعنی XNOR، دقیقاً برعکس عمل می‌کند و وقتی ۱ می‌دهد که دو ورودی برابر باشند؛ به همین دلیل XNOR را «مقایسه‌گر برابری یک‌بیتی» می‌نامند.

دو خاصیت کلیدی

اگر یکی از ورودی‌های XOR را روی ۰ ثابت کنی، خروجی دقیقاً برابر ورودی دیگر می‌شود و گیت مثل یک سیم ساده عمل می‌کند. اما اگر همان ورودی را روی ۱ ثابت کنی، خروجی وارونهٔ ورودی دیگر می‌شود. پس XOR در واقع یک وارونگر کنترل‌شده است: با یک بیت فرمان تصمیم می‌گیری داده عبور کند یا وارونه شود. این خاصیت در مدار تفریق‌کننده و در واحد محاسبات پردازنده بسیار به کار می‌آید. خاصیت دوم این است که XOR جابه‌جایی‌پذیر و شرکت‌پذیر است، پس می‌توان چند ورودی را در یک درخت با هم XOR کرد و ترتیب هیچ اهمیتی ندارد.

راه سریع فهم XOR چندورودی: خروجی وقتی ۱ است که «تعداد یک‌های ورودی فرد باشد». به همین دلیل به این مدار «مولد توازن فرد» هم می‌گویند.

مثال عددی حل‌شده

دو عدد چهاربیتی A برابر ۱۰۱۱ و B برابر ۱۰۰۱ را در نظر بگیر که ارزش ده‌دهی‌شان ۱۱ و ۹ است. XOR بیت‌به‌بیت را حساب کن؛ از چپ به راست: ۱ با ۱ برابر است پس ۰؛ ۰ با ۰ برابر است پس ۰؛ ۱ با ۰ متفاوت است پس ۱؛ ۱ با ۱ برابر است پس ۰. نتیجه ۰۰۱۰ یعنی عدد ۲ می‌شود. تعداد یک‌های نتیجه، «فاصلهٔ همینگ» دو عدد است و اینجا برابر ۱ است؛ یعنی این دو عدد فقط در یک بیت با هم فرق دارند. حالا یک بایت کامل را بررسی کن: ۱۰۱۱۰۱۱۰ که ارزش ده‌دهی‌اش ۱۲۸ + ۳۲ + ۱۶ + ۴ + ۲ یعنی ۱۸۲ است. تعداد یک‌های آن را بشمار: در جایگاه‌های هفت، پنج، چهار، دو و یک، یعنی مجموعاً ۵ بیتِ یک. چون ۵ فرد است، XOR هر هشت بیت برابر ۱ می‌شود. اگر بخواهی با روش «توازن زوج» یک بیت کنترلی اضافه کنی، باید آن بیت را ۱ بگذاری تا تعداد کل یک‌ها به ۶ برسد و زوج شود.

مقایسه‌گر و کاربرد واقعی

برای بررسی برابری دو عدد چهاربیتی، هر جفت بیت هم‌جایگاه را به یک XNOR بده؛ خروجی هر XNOR وقتی ۱ است که آن جفت بیت برابر باشند. سپس هر چهار خروجی را به یک گیت AND چهارورودی بده. تنها اگر هر چهار جفت برابر باشند، خروجی نهایی ۱ می‌شود. برای ساخت XOR هشت‌ورودی هم می‌توانی یک درخت بچینی: چهار گیت در لایهٔ اول، دو گیت در لایهٔ دوم و یک گیت در لایهٔ سوم، مجموعاً ۷ گیت با عمق ۳ لایه. اگر هر گیت ۸ نانوثانیه تأخیر داشته باشد، بیت توازن پس از ۳ ضربدر ۸ یعنی ۲۴ نانوثانیه آماده است. همین مدار در پورت سریال رایانه و در حافظه‌های دارای کنترل خطا به کار می‌رود تا خطای تک‌بیتی ناشی از نویز تشخیص داده شود.