Dairesel vardiya - Circular shift

8 elemanlı dairesel kaymaların matrisleri sola ve sağa kaydırılır

Olarak kombinatoryal matematik , bir dairesel kayma bir girdileri yeniden düzenleme işlemidir tuple ya ya da tersi bir işlem gerçekleştirerek sonraki pozisyona diğer tüm kayıtlar değiştirirken, birinci pozisyona son giriş taşıyarak. Dairesel kayma, özel bir tür döngüsel permütasyondur ve bu da özel bir tür permütasyondur . Resmi olarak, dairesel bir kayma, demetteki n girişin bir permütasyonu σ'dır, öyle ki ya

${\displaystyle \sigma (i)\eşdeğer (i+1)}$ modulo n , tüm girişler için i = 1, ..., n

veya

${\displaystyle \sigma (i)\eşdeğer (i-1)}$ modulo n , tüm girişler için i = 1, ..., n .

Arka arkaya, belirli bir başlığın dairesel kaymaları uygulanması sonucu olarak da adlandırılan dairesel kaymaları tuple.

Örneğin, art arda dört demete ( a , b , c , d ) dairesel kaydırmalar uygulamak ,

• ( d , a , b , c ),
• ( c , d , a , b ),
• ( b , c , d , a ),
• ( a , b , c , d ) (orijinal dörtlü demet),

ve sonra dizi tekrar eder; dolayısıyla bu dörtlü demet, dört farklı dairesel kaymaya sahiptir. Ancak, tüm n- tuple'lar n farklı dairesel kaymaya sahip değildir . Örneğin, 4'lü grup ( a , b , a , b ) yalnızca 2 farklı dairesel kaymaya sahiptir. Genel olarak, bir dairesel kaymaların sayısı , n -tuple herhangi biri olabilir bölen bir n tuple girişleri bağlı olarak.

Olarak bilgisayar programlama , bir bit-bazında dönme de dairesel kayma olarak bilinen, kendi işlenen tüm bitlerini değiştirir bir bit işlemdir. Bir aksine aritmetik kayması , dairesel kayma bir numarası'nın işareti bit korumaz veya ayırt kayan noktalı sayı 'ın üs onun gelen significand . Mantıksal kaydırmadan farklı olarak , boş bit konumları sıfırlarla doldurulmaz, ancak diziden kaydırılan bitlerle doldurulur.

Dairesel vardiyaların uygulanması

Dairesel kaydırmalar, bit dizilerine izin vermek için kriptografide sıklıkla kullanılır . Ne yazık ki, gibi birçok programlama dilleri, C , olsa bile hemen hemen tüm, operatörler veya dairesel kayması için standart görevi bulunmayan işlemciler var bit düzeyinde işlem bunun için talimatlar (örneğin Intel x86 ROL ve ROR'a vardır). Ancak, bazı derleyiciler, içsel işlevler aracılığıyla işlemci talimatlarına erişim sağlayabilir . Ek olarak, standart ANSI C kodundaki bazı yapılar, böyle bir talimata sahip CPU'larda "döndürme" montaj dili talimatı için bir derleyici tarafından optimize edilebilir. Çoğu C derleyicisi aşağıdaki deyimi tanır ve onu tek bir 32-bit döndürme talimatına derler.

/*
 * Shift operations in C are only defined for shift values which are
 * not negative and smaller than sizeof(value) * CHAR_BIT.
 * The mask, used with bitwise-and (&), prevents undefined behaviour
 * when the shift count is 0 or >= the width of unsigned int.
 */

#include <stdint.h>  // for uint32_t, to get 32-bit-wide rotates, regardless of the size of int.
#include <limits.h>  // for CHAR_BIT

uint32_t rotl32 (uint32_t value, unsigned int count) {
    const unsigned int mask = CHAR_BIT * sizeof(value) - 1;
    count &= mask;
    return (value << count) | (value >> (-count & mask));
}

uint32_t rotr32 (uint32_t value, unsigned int count) {
    const unsigned int mask = CHAR_BIT * sizeof(value) - 1;
    count &= mask;
    return (value >> count) | (value << (-count & mask));
}

Bu güvenli ve derleyici dostu uygulama, John Regehr tarafından geliştirildi ve Peter Cordes tarafından daha da cilalandı.

Daha basit bir sürüm, genellikle count1 ila 31 bit aralığıyla sınırlı olduğunda görülür :

uint32_t rotl32 (uint32_t value, unsigned int count) {
    return value << count | value >> (32 - count);
}

Bu sürüm tehlikelidir çünkü count0 veya 32 ise, C dili standardında tanımsız davranış olan 32 bitlik bir kaydırma ister . Ancak yine de çalışma eğilimindedir, çünkü çoğu mikroişlemci value >> 32ya 32-bit kaydırma (0 üretir) ya da 0-bit kaydırma (orijinali valueüretir) olarak uygular ve bu uygulamada her ikisi de doğru sonucu üretir.

Misal

0001 0111 bit dizisi bir bit konumunda dairesel bir kaymaya maruz kaldıysa... (aşağıdaki resimlere bakın)

sola verir: 0010 1110 Sol dairesel kaydırma.

sağa doğru ise: 1000 1011. Sağ dairesel kaydırma.

1001 0110 bit dizisi aşağıdaki işlemlere tabi tutulduysa:

Uygulamalar

Döngüsel kodlar , bir kod sözcüğünün dairesel kaymasının her zaman başka bir kod sözcüğü vermesi özelliğine sahip bir tür blok koddur . Bu motive eder aşağıdaki genel tanım: Bir For dize s bir alfabe üzerinde Σ , let vardiya ( ler ) ifade set dairesel vardiya s ve bir dizi için L dizeleri, let vardiya ( L tüm dairesel vardiya kümesi göstermek) L'deki dizelerin sayısı . Eğer L bir siklik kodu, o zaman vites ( L ) ⊆ L ; bu, L'nin döngüsel bir dil olması için gerekli bir koşuldur . İşlem kayması ( L ) biçimsel dil kuramında incelenmiştir . Örneğin, eğer L a, bağlam-dil , o zaman vites ( L ) yeniden bağlama içermez. Ayrıca, L , bir tarafından açıklanan normal ifade uzunluğu n , uzunluk bir normal ifade vardır O ( n, ³ ) tarif eden kaydırma ( L ).

Ayrıca bakınız

• namlu değiştirici
• Bit düzeyinde işlem
• sirkülant
• Lyndon kelime
• Kolye — bir demet gibi, ancak dairesel kaymaların eşdeğer olduğu kabul edilen bir nesne .

Referanslar