DOI: https://doi.org/10.1109/tit.2026.3686745
تاريخ النشر: 2026-04-24
المؤلف: Aditya Narayan Ravi وآخرون
الموضوع الرئيسي: تقنيات تصحيح الأخطاء
نظرة عامة
في هذا البحث، يستقصي المؤلفون قدرة قناة الورق الممزق (TPC)، التي تحاكي سيناريو اتصال حيث يتم تجزئة الرسائل إلى أطوال عشوائية، وإعادة ترتيبها، وحذفها جزئيًا. هذا النموذج ذو صلة خاصة بالتطبيقات في تخزين البيانات الجزيئية والطب الشرعي. يتميز سعة TPC بتعبير مغلق يُشار إليه بـ $F – A$، حيث يمثل $F$ نسبة تغطية الكود المدخل بواسطة الشظايا الناتجة، ويمثل $A$ تكلفة المحاذاة الناتجة عن الإخراج غير المنظم. تمتد الدراسة أيضًا إلى نسخة ضوضائية من TPC، تتضمن ضوضاء ثنائية متناسقة، حيث يتم اشتقاق حدود عليا وسفلى على السعة، مع الحفاظ على هيكل $F – A$.
يستنتج المؤلفون أن سعة TPC المعممة بدون ضوضاء يمكن التعبير عنها باختصار كـ $F – A$، ويقدمون حدودًا للحالة الضوضائية تتماشى تحت ظروف معينة. يقترحون مزيدًا من التحقيق في تضييق هذه الحدود واستكشاف آثار توسيع النموذج إلى كودات ثنائية الأبعاد، مما قد يعزز عملية فك التشفير من خلال الاستفادة من المعلومات المكانية. هذا التمديد ذو صلة خاصة في التطبيقات الجنائية، حيث قد يتم تشفير الرسائل في بعدين، ويقترح المؤلفون أن العمل المستقبلي يجب أن يركز على آثار السعة لمثل هذا النموذج.
نقاش
في هذا القسم، يناقش المؤلفون قناة الورق الممزق (TPC)، وهو نموذج يعمم الأعمال السابقة حول تجزئة الرسائل، خاصة في سياق تخزين بيانات الحمض النووي. يتميز TPC بتجزئة عشوائية للكودات الثنائية إلى قطع ذات أطوال متغيرة، قد يتم فقدان بعضها أثناء النقل. يحدد المؤلفون سعة هذه القناة، المشار إليها بـ \( C \)، والتي يتم التعبير عنها كـ \( C = F_d\{ \log n \} – A_d\{ \log n \} \). هنا، يمثل \( F_d\{g(n)\} \) نسبة تغطية البتات المحتفظ بها، بينما يمثل \( A_d\{g(n)\} \) تكلفة المحاذاة المرتبطة بفهرسة الشظايا. تشير النتائج إلى أن السعة تتأثر بنسبة البتات المحتفظ بها وتكلفة الحفاظ على ترتيب الشظايا.
يمتد المؤلفون أيضًا بتحليلهم إلى نسخة ضوضائية من TPC، تتضمن ضوضاء على مستوى البت تم نمذجتها بواسطة قناة ثنائية متناسقة (BSC). يتكهنون بأن سعة TPC الضوضائية تحتفظ بشكل مشابه، مما يؤدي إلى حدود داخلية وخارجية لمعدلات قابلة للتحقيق. على وجه التحديد، يستخرجون الحد الداخلي \( R_{in} = (1 – H(p)) F \log n / (1 – H(p)) – A \log n / (1 – H(p)) \) والحد الخارجي \( R_{out} = (1 – H(p)) F_d\{ \log n \} – A_d\{ \log n \} / (1 – H(2p)) \). من الجدير بالذكر أنه عندما تتجاوز أطوال الشظايا عتبة معينة، تتماشى سعة TPC الضوضائية مع سعة قناة الخلط الضوضائية، مما يشير إلى أن توزيع أطوال الشظايا يصبح أقل أهمية بعد هذه النقطة.
DOI: https://doi.org/10.1109/tit.2026.3686745
Publication Date: 2026-04-24
Author(s): Aditya Narayan Ravi et al.
Primary Topic: Error Correcting Code Techniques
Overview
In this research, the authors investigate the capacity of the torn-paper channel (TPC), which simulates a communication scenario where messages are fragmented into random lengths, shuffled, and partially deleted. This model is particularly relevant for applications in molecular data storage and forensics. The capacity of the TPC is characterized by a closed-form expression denoted as $F – A$, where $F$ represents the coverage fraction of the input codeword by the output fragments, and $A$ denotes the alignment cost due to the disordered output. The study also extends to a noisy variant of the TPC, incorporating binary symmetric noise, for which upper and lower bounds on capacity are derived, maintaining the $F – A$ structure.
The authors conclude that the capacity of the generalized TPC without noise can be succinctly expressed as $F – A$, and they provide bounds for the noisy case that align under certain conditions. They propose further investigation into tightening these bounds and explore the implications of extending the model to two-dimensional codewords, which could enhance the decoding process by leveraging spatial information. This extension is particularly pertinent in forensic applications, where messages may be encoded in two dimensions, and the authors suggest that future work should focus on the capacity implications of such a model.
Discussion
In this section, the authors discuss the torn-paper channel (TPC), a model that generalizes previous work on message fragmentation, particularly in the context of DNA data storage. The TPC is characterized by the random fragmentation of binary codewords into variable-length pieces, some of which may be lost during transmission. The authors establish the capacity of this channel, denoted as \( C \), which is expressed as \( C = F_d\{ \log n \} – A_d\{ \log n \} \). Here, \( F_d\{g(n)\} \) represents the coverage fraction of retained bits, while \( A_d\{g(n)\} \) denotes the alignment cost associated with indexing the fragments. The results indicate that the capacity is influenced by the fraction of bits retained and the cost of maintaining the order of fragments.
The authors further extend their analysis to a noisy version of the TPC, incorporating bit-level noise modeled by a Binary Symmetric Channel (BSC). They conjecture that the capacity of this noisy TPC retains a similar form, leading to inner and outer bounds for achievable rates. Specifically, they derive the inner bound \( R_{in} = (1 – H(p)) F \log n / (1 – H(p)) – A \log n / (1 – H(p)) \) and the outer bound \( R_{out} = (1 – H(p)) F_d\{ \log n \} – A_d\{ \log n \} / (1 – H(2p)) \). Notably, when the fragment lengths exceed a certain threshold, the capacity of the noisy TPC aligns with that of the noisy shuffling channel, suggesting that the distribution of fragment lengths becomes less significant beyond this point.