Permutation codes
پرموٹیشن کوڈز ایرر کریکشن کوڈز کا ایک خاندان ہے جسے سب سے پہلے سلیپین نے 1965 میں متعارف کرایا تھا۔ اور فلیش میموری اور پاور لائن کمیونیکیشن سے متعلق ان کی ایپلی کیشنز کی وجہ سے کمبینٹوریکس اور انفارمیشن تھیوری دونوں میں وسیع پیمانے پر مطالعہ کیا گیا ہے۔ تعریف اور خصوصیات ایک پرموٹیشن کوڈ کی تعریف سمیٹرک گروپ کے ذیلی سیٹ کے طور پر کی گئی ہے جو لمبائی کے تاروں کے درمیان معمول کے ہیمنگ فاصلے سے مالا مال ہے۔ مزید واضح طور پر، اگر کسی ترتیب میں تغیرات ہیں، تو پھر کسی ترتیب کوڈ کے کم از کم فاصلے کو کم از کم مثبت عدد کے طور پر بیان کیا جاتا ہے جیسے کہ موجود، الگ، اس طرح۔ تعدد کوڈز بعض چینلز کے لیے موزوں ہونے کی ایک وجہ یہ ہے کہ حروف تہجی کی علامتیں ہر کوڈ ورڈ میں صرف ایک بار ظاہر ہوتی ہیں، جو مثال کے طور پر پاور لائن مواصلات کے تناظر میں ہونے والی غلطیوں کو کوڈ ورڈز گلبرٹ-ورشاموف باؤنڈ پر کم اثر انداز کرتی ہیں۔ تعدد کوڈز میں ایک اہم مسئلہ اس کی قیمت کا تعین کرنا ہے، جہاں لمبائی اور کم سے کم فاصلے کے تعدد کوڈ میں کوڈ ورڈز کی زیادہ سے زیادہ تعداد کے طور پر بیان کیا جاتا ہے۔ چھوٹی لمبائی کے علاوہ اس میں بہت کم پیش رفت ہوئی ہے۔ ہم ان تمام تغیرات کے سیٹ کو ظاہر کرنے کے لیے کے ساتھ تعریف کر سکتے ہیں جن میں شناخت سے بالکل فاصلہ ہوتا ہے۔ ساتھ ہی، آرڈر کے انحراف کی تعداد کہاں ہے۔ گلبرٹ-ورشاموف باؤنڈ ایک بہت مشہور اوپری باؤنڈ ہے، اور اب تک کی چھوٹی اقدار کے لیے دیگر حدود کو پیچھے چھوڑتا ہے۔ نظریہ 1: اس معاملے کے لیے اس میں بہتری آئی ہے جہاں جیسا کہ اگلا نظریہ ظاہر کرتا ہے۔ نظریہ 2: اگر کسی عدد کے لیے، تو۔ اور کی چھوٹی اقدار کے لیے، محققین نے کمپیوٹر کی تلاش کی مختلف حکمت عملیاں تیار کی ہیں تاکہ براہ راست کچھ تجویز کردہ آٹومورفزم کے ساتھ تعدد کوڈز تلاش کیے جا سکیں۔ دیگر حدود تعدد کوڈز پر متعدد حدود ہیں، ہم یہاں دو کی فہرست دیتے ہیں۔ گلبرٹ-ورشاموف باؤنڈ امپروومنٹ ایک بہتری گلبرٹ-ورشاموف باؤنڈ میں کی گئی ہے جس پر پہلے ہی اوپر بحث کی جا چکی ہے۔ بعض گرافوں میں پرموٹیشن کوڈز اور آزاد سیٹوں کے درمیان تعلق کا استعمال کرتے ہوئے جب کوڈ کی لمبائی انفینیٹی تک جاتی ہے تو گلبرٹ-ورشاموف کو ایک عنصر کے ذریعے غیر علامتی طور پر بہتر بنایا جا سکتا ہے۔ آئیے کیلی گراف اور میں شناخت کے پڑوس سے متاثر ذیلی گراف کی نشاندہی کریں۔ آئیے تھیوریم 3 میں زیادہ سے زیادہ ڈگری کی نشاندہی کرتے ہیں: چلو اور پھر، کہاں۔ گلبرٹ-ورشاموف باؤنڈ ہے، نظریہ 4: جب فکس کیا جاتا ہے اور انفینٹی پر ہوتا ہے، تو ہمارے پاس لکیری کوڈز کا استعمال کرتے ہوئے لوور باؤنڈ ہوتے ہیں۔ لکیری بلاک کوڈ کا استعمال کرتے ہوئے، کوئی یہ ثابت کر سکتا ہے کہ ڈگری کے سمیٹرک گروپ میں ایک پرموٹیشن کوڈ موجود ہے، جس میں کم از کم فاصلہ اور بڑی کارڈینیلیٹی ہوتی ہے۔ تعدد کوڈ کے لیے ایک نچلی حد جو تعدد کوڈ کی لمبائی اور فاصلے کے بعض نظاموں میں غیر علامتی بہتری فراہم کرتی ہے، ذیل میں زیر بحث ہے۔ سمیٹرک گروپ کے دیئے گئے ذیلی سیٹ کے لیے، ہم کم از کم مکمل طور پر موجود کم از کم فاصلے کے پرموٹیشن کوڈ کی زیادہ سے زیادہ کارڈینالیٹی سے ظاہر کرتے ہیں، یعنی۔ ۔ نظریہ 5: آئیے انٹیجر اس طرح ہوں کہ اور۔ مزید برآں ایک پرائم پاور بنیں اور مثبت انٹیجر بنیں جیسے کہ اور۔ اگر کوئی ایسا کوڈ موجود ہے جس میں ہیمنگ ویٹ کا کوڈ ورڈ ہے، تو جہاں کورلری 1: ہر پرائم پاور کے لیے، ہر کے لیے،۔ کورلری 2: ہر پرائم پاور کے لیے، ہر کے لیے۔ حوالہ جات کی غلطی کا پتہ لگانے اور اصلاح