سجل ردود الفعل الخطية سجل؟

StackOverflow https://stackoverflow.com/questions/3735217

سؤال

في الآونة الأخيرة ، صدمت مرارًا وتكرارًا في مفهوم LFSR ، وأجدها مثيرة للاهتمام للغاية بسبب روابطها مع حقول مختلفة وأيضًا رائعة في حد ذاتها. استغرق الأمر مني بعض الجهد لفهم ، والمساعدة النهائية كانت جيدة حقًا صفحة, ، أفضل بكثير من الخفي (في البداية) دخول ويكيبيديا. لذلك أردت أن أكتب بعض التعليمات البرمجية الصغيرة لبرنامج عمل مثل LFSR. لكي تكون أكثر دقة ، أظهر هذا بطريقة ما كيف يعمل LFSR. إليكم أنظف شيء يمكن أن أتوصل إليه بعد بعض محاولات Lenghtier (Python):

def lfsr(seed, taps):
    sr, xor = seed, 0
    while 1:
        for t in taps:
            xor += int(sr[t-1])
        if xor%2 == 0.0:
            xor = 0
        else:
            xor = 1
        print xor
        sr, xor = str(xor) + sr[:-1], 0
        print sr
        if sr == seed:
            break

lfsr('11001001', (8,7,6,1))      #example

قمت بتسمية "XOR" إخراج وظيفة XOR ، وليس صحيحًا جدًا. ومع ذلك ، فإن هذا يهدف فقط إلى إظهار كيفية الدوران من خلال حالاتها المحتملة ، في الواقع لاحظت أن السجل يمثله سلسلة. ليس الكثير من التماسك المنطقي.

يمكن تحويل هذا بسهولة إلى لعبة لطيفة يمكنك مشاهدتها لساعات (على الأقل يمكنني :-)

def lfsr(seed, taps):
    import time
    sr, xor = seed, 0
    while 1:
        for t in taps:
            xor += int(sr[t-1])
        if xor%2 == 0.0:
            xor = 0
        else:
            xor = 1
        print xor
        print
        time.sleep(0.75)
        sr, xor = str(xor) + sr[:-1], 0
        print sr
        print
        time.sleep(0.75)

ثم أدهشني ، ما فائدة هذا في كتابة البرامج؟ سمعت أنه يمكن أن يولد أرقام عشوائية. هل هذا صحيح؟ كيف؟ لذلك ، سيكون من الرائع إذا استطاع شخص ما:

  • اشرح كيفية استخدام مثل هذا الجهاز في تطوير البرمجيات
  • توصل إلى بعض التعليمات البرمجية ، لدعم النقطة أعلاه أو مثل لي لإظهار طرق مختلفة للقيام بذلك ، بأي لغة

أيضًا ، نظرًا لأن هناك الكثير من الأشياء التعليمية حول هذه القطعة من المنطق والدوائر الرقمية ، فسيكون من الرائع أن يكون هذا مكانًا لـ Noobies (مثلي) للحصول على فهم أفضل لهذا شيء, أو الأفضل ، لفهم ما هو وكيف يمكن أن يكون مفيدًا عند كتابة البرامج. كان ينبغي أن يجعلها ويكي مجتمع؟

ومع ذلك ، إذا كان شخص ما يشعر وكأنه غولف ... اهلا وسهلا بك.

هل كانت مفيدة؟

المحلول

في الواقع ، الخوارزميات القائمة على LFSR شائعة جدا. تعتمد CRC مباشرة على LFSR. بطبيعة الحال ، في فصول علوم الكمبيوتر ، يتحدث الناس عن الحدود الحية عندما يتحدثون عن كيفية قيام قيمة الإدخال بالقيام بالقيمة المتراكمة ، في هندسة Electornics نتحدث عن الصنابير بدلاً من ذلك. هم نفس المصطلحات المختلفة.

CRC32 هو واحد شائع جدا. يتم استخدامه للكشف عن الأخطاء في إطارات Ethernet. هذا يعني أنه عندما نشرت هذه الإجابة ، استخدم جهاز الكمبيوتر الخاص بي خوارزمية قائمة على LFSR لإنشاء تجزئة من حزمة IP حتى يتمكن جهاز التوجيه الخاص بي من التحقق من أن ما ينقله لم يتم تالفه.

ملفات zip و gzip مثال آخر. كلاهما يستخدم CRC للكشف عن الخطأ. يستخدم ZIP CRC32 و GZIP يستخدم كل من CRC16 و CRC32.

CRCs هي في الأساس وظائف التجزئة. وهو جيد بما يكفي لجعل الإنترنت يعمل. مما يعني أن LFSRs هي وظائف تجزئة جيدة إلى حد ما. لست متأكدًا مما إذا كنت تعرف هذا ولكن بشكل عام تعتبر وظائف التجزئة الجيدة مولدات أرقام عشوائية جيدة. لكن الشيء مع LFSR هو أن اختيار الصنابير الصحيحة (متعدد الحدود) مهم جدًا لجودة الرقم العشوائي.

رمزك عمومًا رمز لعبة لأنه يعمل على سلسلة من الأصفار والأصفار. في العالم الحقيقي يعمل LFSR على أجزاء في بايت. كل بايت تدفعه عبر LFSR يغير القيمة المتراكمة للسجل. هذه القيمة هي بشكل فعال فحوصات لجميع البايتات التي تدفعها عبر السجل. طريقتان شائعتان لاستخدام هذه القيمة كرقم عشوائي هو إما استخدام عداد ودفع سلسلة من الأرقام من خلال السجل ، وبالتالي تحويل التسلسل الخطي 1،2،3،4 إلى بعض تسلسل التجزئة مثل 15306،22،5587 ، 994 ، أو لتغذية القيمة الحالية في السجل لإنشاء رقم جديد في تسلسل عشوائي على ما يبدو.

تجدر الإشارة إلى أن القيام بذلك بسذاجة باستخدام LFSR البتات بطيئة للغاية حيث يتعين عليك معالجة البتات في وقت واحد. لذلك توصل الناس إلى طرق باستخدام الجداول المحسوبة مسبقًا للقيام بذلك ثمانية بتات في وقت واحد أو حتى 32 بت في كل مرة. هذا هو السبب في أنك لا ترى رمز LFSR في البرية. في معظم رمز الإنتاج ، يتنكر كشيء آخر.

ولكن في بعض الأحيان يمكن أن يكون LFSR LFSR البطيء في متناول يدي. لقد كتبت مرة أ Modbus سائق ل mic micro وهذا البروتوكول استخدم CRC16. يتطلب الجدول المحسوب مسبقًا 256 بايت من الذاكرة ولم يكن لوحدة المعالجة المركزية سوى 68 بايت (انا لا امزح). لذلك اضطررت لاستخدام LFSR.

نصائح أخرى

منذ أن كنت أبحث عن تنفيذ LFSR في بيثون ، تعثرت على هذا الموضوع. ومع ذلك ، فقد وجدت أن ما يلي كان أكثر دقة قليلاً وفقًا لاحتياجاتي:

def lfsr(seed, mask):
    result = seed
    nbits = mask.bit_length()-1
    while True:
        result = (result << 1)
        xor = result >> nbits
        if xor != 0:
            result ^= mask

        yield xor, result

يعتمد المولد LFSR أعلاه على GF (2ك) حساب التفاضل والتكامل المعامل (GF = حقل Galois). بعد أن أكملت للتو دورة الجبر ، سأشرح هذه الطريقة الرياضية.

لنبدأ بأخذ ، على سبيل المثال ، GF (24) ، والتي تساوي {أ4x4 + أ3x3 + أ2x2 + أ1x1 + أ0x0 | أ0, ، أ1, ، ...، أ4 ∈ z2} (للتوضيح ، zن = {0،1 ، ... ، n-1} وبالتالي z2 = {0،1} ، أي بت واحد). هذا يعني أن هذه هي مجموعة من جميع الحدود المتعددة من الدرجة الرابعة مع وجود جميع العوامل إما حاضرًا أم لا ، ولكن ليس لها أي مضاعفات من هذه العوامل (على سبيل المثال ، لا يوجد 2xك). x3, ، x4 + x3, ، 1 و x4 + x3 + x2 + x + 1 كلها أمثلة لأعضاء هذه المجموعة.

نأخذ هذا المعامل المحدد متعدد الحدود من الدرجة الرابعة (أي ، p (x) ∈ GF (24)) ، مثل P (x) = x4+x1+x0. كما تم الإشارة إلى عملية المعامل هذه على المجموعة باسم GF (24) / P (x). للرجوع إليها ، يصف P (x) "الصنابير" داخل LFSR.

نأخذ أيضًا متعدد الحدود العشوائية من الدرجة 3 أو أقل (بحيث لا يتأثر بمعاملنا ، وإلا يمكننا أن نفعل أيضًا عملية المعامل مباشرة عليها) ، على سبيل المثال0(x) = x0. الآن كل لاحقأنا(x) يتم حسابه عن طريق ضربه مع x: أأنا(x) = أI-1(x) * x mod p (x).

نظرًا لأننا في حقل محدود ، فقد يكون لعملية المعامل تأثير ، ولكن فقط عندما الناتجةأنا(x) لديه عامل x على الأقل4 (أعلى عامل لدينا في P (x)). لاحظ أنه نظرًا لأننا نعمل بأرقام في Z2, ، إن إجراء عملية المعامل نفسها ليس أكثر من تحديد ما إذا كان كل أأنا يصبح 0 أو 1 عن طريق إضافة القيمتين من P (x) وأنا(x) معا (أي ، 0+0 = 0 ، 0+1 = 1 ، 1+1 = 0 ، أو "Xoring 'هذين).

يمكن كتابة كل متعدد الحدود كمجموعة من البتات ، على سبيل المثال x4+x1+x0 ~ 10011. و0(x) يمكن اعتبارها البذرة. يمكن اعتبار عملية "Times X" بمثابة عملية تحول اليسار. يمكن اعتبار عملية المعامل عملية إخفاء بعض الشيء ، حيث يكون القناع هو p (x).

وبالتالي فإن الخوارزمية الموضحة أعلاه تولد (دفق غير محدود من) أنماط LFSR 4 بتات صالحة. على سبيل المثال ، بالنسبة لنا المحدد أ0(س) (x0) و P (x) (x4+x1+x0), ، يمكننا تحديد النتائج الأولى التي تم إنتاجها التالية في GF (24) (لاحظ أن أ0 لم يتم إنتاجه حتى في نهاية الجولة الأولى - يبدأ علماء الرياضيات عمومًا في العد في "1"):

 i   Ai(x)                   'x⁴'  bit pattern
 0   0x³ + 0x² + 0x¹ + 1x⁰   0     0001        (not yielded)
 1   0x³ + 0x² + 1x¹ + 0x⁰   0     0010
 2   0x³ + 1x² + 0x¹ + 0x⁰   0     0100
 3   1x³ + 0x² + 0x¹ + 0x⁰   0     1000
 4   0x³ + 0x² + 1x¹ + 1x⁰   1     0011        (first time we 'overflow')
 5   0x³ + 1x² + 1x¹ + 0x⁰   0     0110
 6   1x³ + 1x² + 0x¹ + 0x⁰   0     1100
 7   1x³ + 0x² + 1x¹ + 1x⁰   1     1011
 8   0x³ + 1x² + 0x¹ + 1x⁰   1     0101
 9   1x³ + 0x² + 1x¹ + 0x⁰   0     1010
10   0x³ + 1x² + 1x¹ + 1x⁰   1     0111
11   1x³ + 1x² + 1x¹ + 0x⁰   0     1110
12   1x³ + 1x² + 1x¹ + 1x⁰   1     1111
13   1x³ + 1x² + 0x¹ + 1x⁰   1     1101
14   1x³ + 0x² + 0x¹ + 1x⁰   1     1001
15   0x³ + 0x² + 0x¹ + 1x⁰   1     0001        (same as i=0)

لاحظ أن قناعك يجب أن يحتوي على "1" في الموضع الرابع للتأكد من أن LFSR يولد نتائج أربع بت. لاحظ أيضًا أن "1" يجب أن يكون موجودًا في موضع Zeroth للتأكد من أن Bitstream لن ينتهي بنمط 0000 بت ، أو أن البت النهائي سيصبح غير مستخدم (إذا تم نقل جميع البتات إلى اليسار ، فستفعل ذلك ينتهي الأمر أيضًا بصفر في المركز 0 بعد تحول واحد).

ليس كل P (x) بالضرورة مولدات لـ GF (2ك) (أي ، ليس كل أقنعة البتات K تولد كل 2K-1-1 الأرقام). على سبيل المثال ، x4 + x3 + x2 + x1 + x0 يولد 3 مجموعات من 5 متعدد الحدود كل منها ، أو "3 دورات من الفترة 5": 0001،0010،0100،1000،1111 ؛ 0011،0110،1100،01111110 ؛ و 0101،1010،1011،1001،1101. لاحظ أنه لا يمكن إنشاء 0000 ، ولا يمكن إنشاء أي رقم آخر.

عادةً ما يكون ناتج LFSR هو الشيء الذي يتم "تحويله" ، وهو "1" إذا تم إجراء عملية المعامل ، و "0" عندما لا تكون كذلك. LFSR مع فترة 2K-1-1 ، الذي يسمى أيضًا Pseudo-Noise أو PN-LFSR ، يلتزم بعشوائية Golomb ، والتي تقول بقدر ما يكون هذا الناتج عشوائيًا "بما فيه الكفاية".

لذلك فإن تسلسل هذه البتات لها استخدامها في التشفير ، على سبيل المثال في معايير تشفير الهاتف المحمول A5/1 و A5/2 ، أو معيار Bluetooth E0. ومع ذلك ، فهي ليست آمنة كما يريد المرء: خوارزمية Berlekamp-Massey يمكن استخدامها لعكس هندسة متعدد الحدود المميزة (P (x)) من LFSR. لذلك فإن معايير التشفير القوية تستخدم FSR غير الخطيةأو وظائف غير خطية مماثلة. موضوع ذي صلة بهذا هو S- صناديق تستخدم في AES.

لاحظ أنني استخدمت int.bit_length() عملية. لم يتم تنفيذ هذا حتى Python 2.7.
إذا كنت ترغب فقط في نمط بتات محدودة ، فيمكنك التحقق مما إذا كانت البذور تساوي النتيجة ثم كسر حلقةك.
يمكنك استخدام طريقة LFSR في حلقة (على سبيل المثال for xor, pattern in lfsr(0b001,0b10011)) أو يمكنك استدعاء مرارا وتكرارا .next() العملية على نتيجة الطريقة ، وإعادة جديدة (xor, result)-ر في كل مرة.

هناك العديد من تطبيقات LFSRs. أحدها يولد ضوضاء ، على سبيل المثال SN76489 والمتغيرات (المستخدمة في النظام الرئيسي ، معدات اللعبة ، Megadrive ، Neogeo Pocket ، ...) استخدم LFSR لتوليد ضوضاء بيضاء/دورية. هناك وصف جيد حقًا لـ SN76489's LFSR في هذه الصفحة.

لجعلها أنيقة حقًا وأنيقًا ، حاول إنشاء مولد ، yield-القيم المتعاقبة من LFSR. أيضا ، مقارنة بالنقطة العائمة 0.0 غير ضروري ومربك.

LFSR هي مجرد واحدة من العديد من الطرق لإنشاء أرقام عشوائية زائفة في أجهزة الكمبيوتر. العشوائية الزائفة ، لأنه لا توجد أرقام حقًا عشوائي - يمكنك تكرارها بسهولة من خلال البدء مع البذور (القيمة الأولية) والمضي قدمًا في نفس العمليات الرياضية.

فيما يلي تباين في الكود الخاص بك باستخدام الأعداد الصحيحة والمشغلين الثنائيين بدلاً من الأوتار. كما أنه يستخدم العائد كما اقترح شخص ما.

def lfsr2(seed, taps):
    sr = seed
    nbits = 8
    while 1:
        xor = 1
        for t in taps:
            if (sr & (1<<(t-1))) != 0:
                xor ^= 1
        sr = (xor << nbits-1) + (sr >> 1)
        yield xor, sr
        if sr == seed:
            break

nbits = 8
for xor, sr in lfsr2(0b11001001, (8,7,6,1)):
    print xor, bin(2**nbits+sr)[3:]

إذا افترضنا أن البذور هي قائمة من ints بدلاً من سلسلة (أو تحويلها إذا لم تكن كذلك) ، فيجب أن يفعل ما يلي ما تريد مع المزيد من الأناقة:

def lfsr(seed, taps) :
  while True:
    nxt = sum([ seed[x] for x in taps]) % 2
    yield nxt
    seed = ([nxt] + seed)[:max(taps)+1]

مثال :

for x in lfsr([1,0,1,1,1,0,1,0,0],[1,5,6]) :
  print x

list_init=[1,0,1,1]
list_coeff=[1,1,0,0]
out=[]
for i in range(15):
    list_init.append(sum([list_init[i]*list_coeff[i] for i in range(len(list_init))])%2)
    out.append(list_init.pop(0))
print(out)

#https://www.rocq.inria.fr/secret/Anne.Canteaut/encyclopedia.pdf
مرخصة بموجب: CC-BY-SA مع الإسناد
لا تنتمي إلى StackOverflow
scroll top