الكود القطبي (نظرية الترميز)

في نظرية المعلومات ، تعد الأكواد القطبية عبارة عن أكواد تصحيح أخطاء كتلة خطية . يعتمد بناء الكود على تسلسل متكرر متعدد لكود نواة قصير يحول القناة المادية إلى قنوات خارجية افتراضية. عندما يصبح عدد التكرارات كبيرًا، تميل القنوات الافتراضية إلى أن تكون ذات موثوقية عالية أو موثوقية منخفضة (بعبارة أخرى، تستقطب أو تصبح متفرقة)، ويتم تخصيص بتات البيانات للقنوات الأكثر موثوقية. إنه أول كود ذو بناء صريح لتحقيق سعة القناة بشكل يمكن إثباته للقنوات المنفصلة عديمة الذاكرة ذات المدخلات الثنائية المتماثلة (B-DMC) مع الاعتماد متعدد الحدود على فجوة السعة. ^[1] تم تطوير الأكواد القطبية بواسطة إردال أريكان ، أستاذ الهندسة الكهربائية في جامعة بيلكنت .

من الجدير بالذكر أن الشفرات القطبية لها تعقيد ترميز وفك تشفير متواضع $O (n log n)$ ، مما يجعلها جذابة للعديد من التطبيقات. علاوة على ذلك، يمكن أن يصل تعقيد طاقة الترميز وفك التشفير للشفرات القطبية المعممة إلى الحدود الدنيا الأساسية لاستهلاك الطاقة للدوائر ثنائية الأبعاد إلى ما يقرب من عامل $O (n ε polylog n)$ لأي $ε > 0.$ ^[2]

التطبيقات الصناعية

تحتوي أكواد القطبية على بعض القيود عند استخدامها في التطبيقات الصناعية. في المقام الأول، يحقق التصميم الأصلي للأكواد القطبية السعة عندما تكون أحجام الكتل كبيرة بشكل مقارب مع فك تشفير الإلغاء المتتالي. ومع ذلك، مع أحجام الكتل المستخدمة في الصناعة، يكون أداء الإلغاء المتتالي ضعيفًا مقارنة بمخططات الترميز المحددة والمنفذة جيدًا مثل كود التحقق من التكافؤ منخفض الكثافة (LDPC) وكود توربو . يمكن تحسين أداء القطبية باستخدام فك تشفير قائمة الإلغاء المتتالي، لكن قابلية استخدامه في التطبيقات الحقيقية لا تزال موضع تساؤل بسبب ضعف كفاءة التنفيذ الناتجة عن النهج التكراري. ^[3]

في أكتوبر 2016، أعلنت شركة هواوي أنها حققت 27 جيجابت/ثانية في اختبارات التجارب الميدانية لشبكة الجيل الخامس باستخدام أكواد القطبية لترميز القناة. وقد تم تقديم التحسينات بحيث أغلق أداء القناة الآن الفجوة تقريبًا مع حد شانون ، والذي يحدد الحد الأقصى للمعدل لنطاق ترددي معين ومستوى ضوضاء معين. ^[4]

في نوفمبر 2016، وافقت 3GPP على اعتماد أكواد قطبية لقنوات التحكم eMBB (النطاق العريض المتنقل المحسن) لواجهة 5G NR (الراديو الجديد). وفي نفس الاجتماع، وافقت 3GPP على استخدام LDPC لقناة البيانات المقابلة. ^[5]^[6]

رموز PAC

في عام 2019، اقترح أريكان استخدام تحويل مسبق التفافي قبل الترميز القطبي. أُطلق على هذه المتغيرات المحولة مسبقًا للرموز القطبية اسم رموز التفافية معدلة الاستقطاب (PAC). ^[7] وقد ثبت أن التحويل المسبق يمكن أن يحسن بشكل فعال خصائص المسافة للرموز القطبية عن طريق تقليل عدد الكلمات الرمزية ذات الوزن الأدنى والوزن الصغير بشكل عام، ^[8] مما يؤدي إلى تحسين معدلات خطأ الكتلة تحت خوارزمية فك التشفير شبه الأقصى (ML) مثل فك تشفير فانو وفك تشفير القائمة. ^[9] فك تشفير فانو هو خوارزمية بحث شجري تحدد كلمة الرمز المنقولة باستخدام دالة مترية مثالية لتوجيه عملية البحث بكفاءة. ^[10] رموز PAC تعادل أيضًا رموز القطبية بعد التحويل مع رموز دورية معينة. ^[11] عند أطوال كتلة قصيرة، تتفوق هذه الرموز على كل من الرموز التفافية وفك تشفير القائمة بمساعدة CRC للرموز القطبية التقليدية. ^[12]^[13]

فك تشفير القطبية العصبية

إن أجهزة فك التشفير القطبية العصبية (NPDs) ^[14] هي تقدم في ترميز القنوات التي تجمع بين الشبكات العصبية (NNs) والرموز القطبية، مما يوفر فك تشفير موحد للقنوات مع أو بدون ذاكرة، دون الحاجة إلى نموذج قناة صريح. وهي تستخدم أربع شبكات عصبية لتقريب وظائف فك التشفير القطبي: الشبكة العصبية للتضمين (E) والشبكة العصبية للعقدة (F) والشبكة العصبية للعقدة (G) والشبكة العصبية للتضمين إلى LLR (H). يتم تحديد أوزان هذه الشبكات العصبية من خلال تقدير المعلومات المتبادلة للقنوات الاصطناعية. وبحلول نهاية التدريب، يتم تثبيت أوزان NPD ويمكن استخدامها بعد ذلك لفك التشفير.

يتم تحديد التعقيد الحسابي لـ NPDs من خلال معلمة الشبكات العصبية، على عكس مفككي التعريشات بالإلغاء المتتالي (SC)، ^[15] حيث يتم تحديد تعقيدها من خلال نموذج القناة وتستخدم عادةً للقنوات ذات الحالة المحدودة (FSCs). التعقيد الحسابي لـ NPDs هو ، حيث هو عدد الوحدات المخفية في الشبكات العصبية، هو بُعد التضمين، و هو طول الكتلة. في المقابل، فإن التعقيد الحسابي لمفككي تعريشات SC هو ، حيث هي مساحة حالة نموذج القناة. ${\textstyle O(kdN\log _{2}N)}$ $k$ $د$ $N$ $O(|{\mathcal {S}}|^{3}N\log _{2}N)$ ${\mathcal {S}}$

يمكن دمج NPDs في مخططات فك تشفير SC ^[1] مثل فك تشفير قائمة SC وفك تشفير SC بمساعدة CRC. ^[16] كما أنها متوافقة مع توزيعات الإدخال غير المنتظمة والمتماثلة من خلال دمجها في مخطط Honda-Yamamoto. ^[17] تسمح هذه المرونة باستخدام NPDs في سيناريوهات فك التشفير المختلفة، مما يحسن أداء تصحيح الأخطاء مع الحفاظ على التعقيد الحسابي القابل للإدارة.

مراجع

^ ab Arikan, Erdal (2009). "Channel Polarization: A Method for Constructing Capacity-Achieving Codes for Symmetric Binary-Input Memoryless Channels". معاملات معهد مهندسي الكهرباء والإلكترونيات في نظرية المعلومات . 55 (7): 3051–3073. arXiv : 0807.3917 . doi :10.1109/TIT.2009.2021379. ISSN 0018-9448.
^ بليك، كريستوفر ج. (2017). "استهلاك الطاقة لدوائر ترميز التحكم في الأخطاء" (PDF) . جامعة تورنتو . تم الاسترجاع في 2019-10-18 .
^ أريكان، إردال؛ نجيب الحسن؛ لينتماير، مايكل. مونتورسي، جويدو؛ ساير، جوسي (2015). “التحديات وبعض الاتجاهات الجديدة في تشفير القنوات”. أرخايف : 1504.03916 [cs.IT].
^ "هواوي تحقق سرعات 27 جيجابت في الثانية لشبكة الجيل الخامس مع Polar Code" . تم الاسترجاع في 10 أكتوبر 2016 .
^ "التقرير النهائي لاجتماع 3GPP RAN1 رقم 87". 3GPP . تم الاسترجاع في 31 أغسطس 2017 .^{[ رابط معطل ]}
^ م. روشان، م. تشيو، ي. شيه، إكس. جو وجيه يوان، "ترميز القنوات نحو الجيل السادس: نظرة عامة وتوقعات تقنية"، في مجلة IEEE المفتوحة لجمعية الاتصالات ، المجلد 5، ص 2585-2685، 2024، doi: 10.1109/OJCOMS.2024.3390000.
^ E. Arıkan, "From sequential decoding to channel polarization and back again", 2019, arXiv:1908.09594
^ م. روشان وج. يوان، "حول كلمات رمز الوزن الأدنى لرموز PAC: تأثير ما قبل التحويل"، في مجلة IEEE حول مناطق مختارة في نظرية المعلومات ، المجلد 4، ص 487-498، 2023، doi: 10.1109/JSAIT.2023.3312678.
^ م. روشان، أ. بورج وإي. فيتربو، "رموز الالتواء المعدلة بالاستقطاب (PAC): فك التشفير المتسلسل مقابل فك التشفير بالقائمة"، في معاملات معهد مهندسي الكهرباء والإلكترونيات لتكنولوجيا المركبات ، المجلد 70، العدد 2، ص 1434-1447، فبراير 2021، doi: 10.1109/TVT.2021.3052550.
^ م. مورادي، "حول دالة فك التشفير المتسلسلة للرموز التلافيفية المعدلة بالاستقطاب (PAC)"، معاملات معهد مهندسي الكهرباء والإلكترونيات في مجال الاتصالات، المجلد 69، العدد 12، ص 7913-7922، 2021، doi: 10.1109/TCOMM.2021.3111018.
^ م. مورادي، "الرموز التلافيفية المعدلة بالاستقطاب (PAC) كتسلسل للرموز الدائرية الداخلية والرموز القطبية الخارجية ورموز ريد-مولر الشبيهة"، الحقول المحدودة وتطبيقاتها، المجلد 93، ص 102321، 2024، doi: https://doi.org/10.1016/j.ffa.2023.102321.
^ مرادي، محسن؛ مزمل، أمير؛ تشين، كانججيان؛ أريكان، إردال (2020). “أداء وتعقيد فك التشفير المتسلسل لرموز PAC”. أرخايف : 2012.04990 [cs.IT].
^ ياو، هانوين؛ فازيلي، أرمان؛ فاردي، ألكسندر (2021). "فك رموز قائمة PAC الخاصة بأريكان". Entropy . 23 (7): 841. arXiv : 2005.13711 . Bibcode : 2021Entrp..23..841Y . doi : 10.3390/e23070841 . PMC 8303677. PMID 34209050.
^ أهاروني، زيف؛ هوليهيل، باشار؛ فيستر، هنري د؛ بيرموتير، حاييم هـ. (2023-09-06). "الرموز القطبية العصبية المعتمدة على البيانات للقنوات غير المعروفة مع الذاكرة وبدونها". arXiv : 2309.03148 [cs.IT].
^ وانج، رونكسين؛ هوندا، جونيا؛ ياماموتو، هيروسوكي؛ ليو، رونغكي؛ هو، يي (2015). "إنشاء أكواد قطبية للقنوات ذات الذاكرة". ورشة عمل نظرية المعلومات IEEE 2015 - الخريف (ITW) . IEEE. ص. 187-191. doi :10.1109/ITWF.2015.7360760. ISBN 978-1-4673-7852-9.
^ تال، إيدو؛ فاردي، ألكسندر (2015). "فك رموز القائمة القطبية". معاملات معهد مهندسي الكهرباء والإلكترونيات في نظرية المعلومات . 61 (5): 2213-2226. arXiv : 1206.0050 . doi : 10.1109/TIT.2015.2410251. ISSN 0018-9448.
^ هوندا، جونيا؛ ياماموتو، هيروسوكي (2013). "الترميز القطبي بدون امتداد أبجدي للنماذج غير المتماثلة". معاملات معهد مهندسي الكهرباء والإلكترونيات في نظرية المعلومات . 59 (12): 7829-7838. doi :10.1109/TIT.2013.2282305. ISSN 0018-9448.

روابط خارجية

الصفحة الرئيسية لبرنامج AFF3CT: مجموعة أدوات تصحيح الأخطاء السريعة لمحاكاة الكود القطبي عالي السرعة في البرامج

Original text

Rate this translation

Your feedback will be used to help improve Google Translate

[:0-1] Arikan, Erdal (2009). "Channel Polarization: A Method for Constructing Capacity-Achieving Codes for Symmetric Binary-Input Memoryless Channels". معاملات معهد مهندسي الكهرباء والإلكترونيات في نظرية المعلومات . 55 (7): 3051–3073. arXiv : 0807.3917 . doi :10.1109/TIT.2009.2021379. ISSN 0018-9448.

[2] بليك، كريستوفر ج. (2017). "استهلاك الطاقة لدوائر ترميز التحكم في الأخطاء" (PDF) . جامعة تورنتو . تم الاسترجاع في 2019-10-18 .

[:1-3] أريكان، إردال؛ نجيب الحسن؛ لينتماير، مايكل. مونتورسي، جويدو؛ ساير، جوسي (2015). “التحديات وبعض الاتجاهات الجديدة في تشفير القنوات”. أرخايف : 1504.03916 [cs.IT].

[:2-4] "هواوي تحقق سرعات 27 جيجابت في الثانية لشبكة الجيل الخامس مع Polar Code" . تم الاسترجاع في 10 أكتوبر 2016 .

[:3-5] "التقرير النهائي لاجتماع 3GPP RAN1 رقم 87". 3GPP . تم الاسترجاع في 31 أغسطس 2017 .^{[ رابط معطل ]}

[6] م. روشان، م. تشيو، ي. شيه، إكس. جو وجيه يوان، "ترميز القنوات نحو الجيل السادس: نظرة عامة وتوقعات تقنية"، في مجلة IEEE المفتوحة لجمعية الاتصالات ، المجلد 5، ص 2585-2685، 2024، doi: 10.1109/OJCOMS.2024.3390000.

[7] E. Arıkan, "From sequential decoding to channel polarization and back again", 2019, arXiv:1908.09594

[8] م. روشان وج. يوان، "حول كلمات رمز الوزن الأدنى لرموز PAC: تأثير ما قبل التحويل"، في مجلة IEEE حول مناطق مختارة في نظرية المعلومات ، المجلد 4، ص 487-498، 2023، doi: 10.1109/JSAIT.2023.3312678.

[9] م. روشان، أ. بورج وإي. فيتربو، "رموز الالتواء المعدلة بالاستقطاب (PAC): فك التشفير المتسلسل مقابل فك التشفير بالقائمة"، في معاملات معهد مهندسي الكهرباء والإلكترونيات لتكنولوجيا المركبات ، المجلد 70، العدد 2، ص 1434-1447، فبراير 2021، doi: 10.1109/TVT.2021.3052550.

[10] م. مورادي، "حول دالة فك التشفير المتسلسلة للرموز التلافيفية المعدلة بالاستقطاب (PAC)"، معاملات معهد مهندسي الكهرباء والإلكترونيات في مجال الاتصالات، المجلد 69، العدد 12، ص 7913-7922، 2021، doi: 10.1109/TCOMM.2021.3111018.

[11] م. مورادي، "الرموز التلافيفية المعدلة بالاستقطاب (PAC) كتسلسل للرموز الدائرية الداخلية والرموز القطبية الخارجية ورموز ريد-مولر الشبيهة"، الحقول المحدودة وتطبيقاتها، المجلد 93، ص 102321، 2024، doi: https://doi.org/10.1016/j.ffa.2023.102321.

[:4-12] مرادي، محسن؛ مزمل، أمير؛ تشين، كانججيان؛ أريكان، إردال (2020). “أداء وتعقيد فك التشفير المتسلسل لرموز PAC”. أرخايف : 2012.04990 [cs.IT].

[13] ياو، هانوين؛ فازيلي، أرمان؛ فاردي، ألكسندر (2021). "فك رموز قائمة PAC الخاصة بأريكان". Entropy . 23 (7): 841. arXiv : 2005.13711 . Bibcode : 2021Entrp..23..841Y . doi : 10.3390/e23070841 . PMC 8303677. PMID 34209050.

[14] أهاروني، زيف؛ هوليهيل، باشار؛ فيستر، هنري د؛ بيرموتير، حاييم هـ. (2023-09-06). "الرموز القطبية العصبية المعتمدة على البيانات للقنوات غير المعروفة مع الذاكرة وبدونها". arXiv : 2309.03148 [cs.IT].

[15] وانج، رونكسين؛ هوندا، جونيا؛ ياماموتو، هيروسوكي؛ ليو، رونغكي؛ هو، يي (2015). "إنشاء أكواد قطبية للقنوات ذات الذاكرة". ورشة عمل نظرية المعلومات IEEE 2015 - الخريف (ITW) . IEEE. ص. 187-191. doi :10.1109/ITWF.2015.7360760. ISBN 978-1-4673-7852-9.

[16] تال، إيدو؛ فاردي، ألكسندر (2015). "فك رموز القائمة القطبية". معاملات معهد مهندسي الكهرباء والإلكترونيات في نظرية المعلومات . 61 (5): 2213-2226. arXiv : 1206.0050 . doi : 10.1109/TIT.2015.2410251. ISSN 0018-9448.

[17] هوندا، جونيا؛ ياماموتو، هيروسوكي (2013). "الترميز القطبي بدون امتداد أبجدي للنماذج غير المتماثلة". معاملات معهد مهندسي الكهرباء والإلكترونيات في نظرية المعلومات . 59 (12): 7829-7838. doi :10.1109/TIT.2013.2282305. ISSN 0018-9448.